[C] Generare tutte le permutazioni con approccio iterativo

[quadamge]

Mi chiedevo da un bel po' di tempo come è possibile realizzare un algoritmo in C che generi tutte le permutazioni di una sequenza di elementi distinti, senza l'ausiolio dell'approccio ricorsivo, insomma un'impresa quasi impossibile. Chi è che si è avventurato in questo rompicapo?

Grazie mille per i suggerimenti.

[unomichisiada]

Originariamente inviato da quadamge
Mi chiedevo da un bel po' di tempo come è possibile realizzare un algoritmo in C che generi tutte le permutazioni di una sequenza di elementi distinti, senza l'ausiolio dell'approccio ricorsivo, insomma un'impresa quasi impossibile. Chi è che si è avventurato in questo rompicapo?

Grazie mille per i suggerimenti.

impossibile non è di certo

[netarrow]

se parti da

0
1
2
3

Nella prima posizione potrai mettere 4 elementi: 0,1,2 o 3, per ogni elementi messo al primo posto potrai avere 3 elementi alla seconda posizione visto che un elemento è già sistemato, per ogni coppia formata dalla prima e seconda posizione potrai avere in terza 2 possibilità visto che due sono già sistemati, infine te ne resta 1, ed ecco che otteniamo 4!=4*3*2*1=24.

Dando per scontato che magari questo lo sapevi già e che me lo sono scritto per chiarirmi le idee io se hai l'algoritmo ricorsivo magari è più semplice tradurlo in iterativo piuttosto che riscriverlo ex novo.

Io ho sentito parlare di strutture ad albero,grafi e simili che non so perchè mi sembri che c'entrino qualcosa con tutto questo e che potrebbero essere utili.

Io per ora ho riassunto il tutto cos':

0-1-2-3
1-0-2-3
2-0-1-3
3-0-1-2

Crei una matrice n*n come sopra, prendi tutti gli elementi della prima riga e scrivi il primo, poi passi alla seconda riga, li scrivi tutti tranne quello scritto nelle prima, poi alla terza scrivi tutti tranne quelli già usati e così via

Non so a prestazioni cosa viene fuori, se è giusto... però prova e sappimi dire(ora quasi quasi provo pure io)

[Mutato]

Originariamente inviato da quadamge
Mi chiedevo da un bel po' di tempo come è possibile realizzare un algoritmo in C che generi tutte le permutazioni di una sequenza di elementi distinti, senza l'ausiolio dell'approccio ricorsivo, insomma un'impresa quasi impossibile. Chi è che si è avventurato in questo rompicapo?

Grazie mille per i suggerimenti.

Mi interessai al problema qui:
http://forum.html.it/forum/showthrea...hreadid=939384

In realta' io cercavo le combinazioni senza ripetizioni, ma il problema e' piu' o meno il medesimo, l'unica vera differenza e' che mentre una permutazione e' ordinata, una combinazione non lo e' necessariamente.

Non so se esista un metodo che consenta di fare a meno della ricorsione, probabilmente no, anche se forse potrebbe essere interessante una ricorsione intelligente, cioe' non statica come quella in esempio, ma in grado di autoderminarsi a partire dalla posizione degli elementi della stringa appena elaborata o fornita.

[netarrow]

ma ora ho un dubbio, dal punto di vista teorico, al 100% qualciasi algoritmo può essere implementato sia ricorsivamente sia iterativamente?

[quadamge]

Così afferma il mio prof. di Programmazione.

[unomichisiada]

Originariamente inviato da netarrow
ma ora ho un dubbio, dal punto di vista teorico, al 100% qualciasi algoritmo può essere implementato sia ricorsivamente sia iterativamente?

Ma certo! E' anche normal se pensi a come funziona la ricorsione. Si tratta sostanzialmente dell'uso opportuno di una struttura dati: lo stack. Se invece di usare lo stack di sistema con la ricorsione, usi uno stack software (non è detto che ciò sia necessario per la conversione di un algoritmo ricorsivo in iterativo) riesci sicuramente a realizzare la conversione.

[netarrow]

crei un grafo per ogni elemento, tipo

     3 - 4
    /
   2 - 4 - 3  
  /   2 - 4
 /   /
1 - 3 - 4 - 2
 \ 
  4 - 3 - 2
   \ 
    2 - 3

e stampi ogni strada possibile, si può fare no?

poi per gli altri non basta sostituire il primo elemento con quello attuale? se ad esempio tocca vedere le combinazioni che iniziano per 2 so sostituisce 1 dove c'è 2 e 2 dove c'è 1.

[netarrow]

Ah eccolo qui, un algoritmo iterativo:

QuickPerm

http://www.geocities.com/permute_it/01example.html

[quadamge]

l'ho provato, funziona! capperi!

Grazie.