#
#
# **Andrea Sterbini**
#
# lezione 22 - 11 dicembre 2023
# %% [markdown] slideshow={"slide_type": "slide"} jp-MarkdownHeadingCollapsed=true
# # RECAP:
# - rappresentazione di **espressioni algebriche**
# - calcolo
# - semplificazione
# - parsing
# %% [markdown] slideshow={"slide_type": "slide"}
# # Combinazioni e permutazioni
# - **combinazioni** di **k** elementi scelti tra **N** valori (CON ripetizioni)
# - **permutazioni** di **k** elementi scelti tra **N** valori (SENZA ripetizioni)
# %% [markdown]
# ## Combinazioni
# Per ottenere una delle possibili combinazioni
# - per k volte
# - scelgo uno dei N valori e lo aggiungo al risultato
#
# Per ottenerle tutte
# - inizio con le soluzioni per N=1, ciascuna contenente uno degli N valori
# - per k-1 volte
# - aggiungo ciascuno degli N valori a tutte le soluzioni già calcolate
# %%
## Versione iterativa
def combinazioni_iterativa(L : list, k : int) -> list:
risultato = [ [X] for X in L ]
for i in range(1,k): # per k-1 volte
nuovo_risultato = [ [Y]+precedente for precedente in risultato
for Y in L ]
risultato = nuovo_risultato
return risultato
# %%
# esempio
print(combinazioni_iterativa([1, 2, 3], 3))
# %% [markdown]
# Per realizzarlo ricorsivo
# - usiamo k come indice del problema e lo riduciamo di 1 mano a mano (**riduzione**)
# - il **caso base** è k==1
# - in questo caso ciascuna combinazione contiene uno solo degli N valori
# - altrimenti basta aggiungere (**composizione**) a tutte le sottosoluzioni ciascuno degli N valori
#
# **convergenza**: da k>0 a forza di togliere 1 si arriva a 1
# %%
## versione ricorsiva
def combinazioni_ricorsiva(L:list, k:int) -> list:
if k == 1:
return [ [X] for X in L ]
else:
return [ [Y]+sottosoluzione for sottosoluzione in combinazioni_ricorsiva(L,k-1)
for Y in L ]
# %%
# esempio
print(combinazioni_ricorsiva([1, 2, 3], 3))
# %% [markdown]
# ## Permutazioni (k elementi SENZA ripetizioni)
# - idea 1: costruisco tutte le combinazioni e TOLGO quelle con ripetizioni
# - inefficiente (meglio NON GENERARE cose che dovremo filtrare)
# - NON FUNZIONA se nella lista degli elementi da permutare ci sono doppioni
# - idea 2:
# - come la generazione delle combinazioni ma stando attenti a non riusare lo stesso elemento
# %% [markdown]
# ## versione ricorsiva
# - come prima, riduciamo su k
# - ma ogni volta che scegliamo un elemento da aggiungere ad una sottosoluzione NON lo passiamo alla chiamata ricorsiva
# %%
def permutazioni_ricorsiva(L:list, k:int) -> list:
assert k <= len(L), f"k={k} è maggiore della lunghezza di L ({len(L)})"
if k==1:
return [ [X] for X in L]
else:
risultato = []
for i in range(len(L)):
resto = L.copy()
Y = resto.pop(i)
#Y = L[i] # prendo l'elemento Y
#resto = L[:i]+L[i+1:] # tolgo Y da L
for sottosoluzione in permutazioni_ricorsiva(resto, k-1): # NOTA: la lista NON contiene l'elemento Y
risultato.append([Y]+sottosoluzione)
return risultato
# %%
# Esempio
print(permutazioni_ricorsiva([1,2,3,4],2))
# %%
# %%
# %% [markdown] slideshow={"slide_type": "slide"}
# # Rotazione ricorsiva di immagini
# - vediamo che succede se divido una immagine in 4 parti e la ruoto
# %%% Rotazione di una immagine quadrata di lato 2^n ricorsivamente [markdown] slideshow={"slide_type": "fragment"}
#