Data una lista di elementi qualsiasi visualizza tutte le liste permutazioni: Pn = n!
1
Prima della chiamata ricorsiva scambia di posizione due elementi.
Dopo la chiamata ricorsiva rimette a posto gli elementi scambiati.
def scambia(lista, p1, p2):
temp = lista[p1]
lista[p1] = lista[p2]
lista[p2] = temp
def permuta(lista, pos, n):
if(pos == n):
print(lista)
else:
for k in range(pos, n):
scambia(lista, pos, k) # <--
permuta(lista, pos+1, n)
scambia(lista, pos, k) # <--
LISTA = [1, 2, 3, 4]
permuta(LISTA, 0, len(LISTA))
2
Lo scambio avviene sulla copia quindi non è necessario rimettere a posto dopo la chiamata ricorsiva.
def scambia(lista, p1, p2):
temp = lista[p1]
lista[p1] = lista[p2]
lista[p2] = temp
def permuta(lista, pos, n):
if(pos == n-1):
print(lista)
else:
for k in range(pos, n):
LISTA=lista[:]
scambia(LISTA, pos, k) # <--
permuta(LISTA, pos+1, n)
LISTA = [1, 2, 3, 4]
permuta(LISTA, 0, len(LISTA))
Permutazioni in ordine?
1
Le liste generate possono essere inserite in una lista che verrà ordinata.
def scambia(lista, p1, p2):
temp = lista[p1]
lista[p1] = lista[p2]
lista[p2] = temp
def permuta(lista, pos, n, elenco):
if(pos == n-1):
elenco.append(lista)
else:
for k in range(pos, n):
scambia(lista, pos, k)
permuta(lista, pos+1, n, elenco)
scambia(lista, pos, k)
LISTA = [1, 2, 3, 4]
ELENCO = []
permuta(LISTA, 0, len(LISTA), ELENCO)
ELENCO.sort()
for x in ELENCO:
print(x)
2
Modificando l’algoritmo è possibile scambiare gli elementi in modo che il risultato sia già ordinato
- La lista iniziale è ordinata
- Lo scambio è diverso…
def scambia(lista, p1, p2):
temp = lista[p1]
lista[p1] = lista[p2]
lista[p2] = temp
def permuta(lista, pos, n):
if(pos == n-1):
print(lista)
else:
for k in range(pos, n):
lista.insert(pos, lista[k]) # <--
del lista[k+1] # <--
permuta(LISTA, pos+1, n)
lista.insert(k+1, lista[pos]) # <--
del lista[pos] # <--
LISTA = [1, 2, 4, 3]
LISTA.sort() # <--
permuta(LISTA, 0, len(LISTA))