Newsgroup: it.comp.lang.c
Titolo: permutazione lista

Qualcuno mi puoi dare qualche indicazione sul seguente problema: data una
lista di n elementi stampare tutte le possibili permutazioni.
Saluti a tutto il NG.
TOny

 ha
scritto:

--
Per scrivermi togliete "111".

 wrote in message
pah2uv8v93iuu1srq...@4ax.com...


 Ciao
umh, questa soluzione e' orribile!
Tommy

 Tony
Certo, ti pare una soluzione quella di utilizzare n cicli nidificati?
Tommy

 Come potrei fare?
Dici bene, il numero di permutazioni di un insieme di grandezza n e' n!.
Ma non ti fare confondere da questo.....
Ti ho scritto un programma che stampa le permutazioni...
Non e' il modo migliore di implementarle, ma credo sia un modo molto
semplice da comprendere.
<CODE>
#include<stdio.h>
char letters[] = {'a','b','c','d','\0'};
// solo per controllare quante stringhe stampiamo...
int number_of_permutations=0;
void Swap(char *c1, char *c2)
{
     char tmp;
     tmp=*c1; *c1=*c2; *c2=tmp;
}
void Permutations(int level, const int size)
{
     int i;
     // se siamo arrivati in fondo, stampiamo la stringa ottenuta
     if(level==size){
          printf("%s\n",letters);
          // aumentiamo il numero cosi' vediamo quante stringhe stiamo
stampando.
          ++number_of_permutations;
     }else{
          // altrimenti permutiamo:
          Permutations(level+1,size);
          for(i=level+1; i<size ;++i){
               Swap((letters+level),(letters+i));
               Permutations(level+1,size);
               Swap((letters+level),(letters+i));
          }
     }
}
int main()
{
     printf("Stringa di partenza: %s\n",letters);
     // 0 e' il livello da cui partiamo
     // 4 e' il numero di elementi che vogliamo permutare
     Permutations(0,4);
     printf("Stringa di arrivo: %s\n",letters);
     printf("Numero di stringhe stampate: %d\n",number_of_permutations);
     return 0;
}
</CODE>
Allora:
char letters[] = {'a','b','c','d','\0'};
rappresenta le lettere che vogliamo permutare. Questo e' un array per
semplicita' e termina con '\0' per rendere piu' semplice stamparlo a video.
Ovviamente il '\0' non e' necessario!
int number_of_permutations=0;
questa var globale serve per vedere quante stringe stampiano (permutazioni).
void Swap(char *c1, char *c2)
questa scampia due elementi.
// 0 e' il livello da cui partiamo
// 4 e' il numero di elementi che vogliamo permutare
Permutations(0,4);
Questa e' la chiamata in main().
in altre parole diciamo, parti dal primo elemento (0) e sappi che ci sono 4
elementi.
Inoltre in main() stampiamo la stringa prima e doppo la permutazione. Questo
serve a dimostrare che ritorna la stessa di prima!
printf("Numero di stringhe stampate: %d\n",number_of_permutations);
Questo serve a dimostrare che stampiamo n! permutazioni.
La funzione Permutations() fa tutto il lavoro:
<FUNCTION>
void Permutations(int level, const int size)
{
     int i;
     // se siamo arrivati in fondo, stampiamo la stringa ottenuta
     if(level==size){
          printf("%s\n",letters);
          // aumentiamo il numero cosi' vediamo quante stringhe stiamo
stampando.
          ++number_of_permutations;
     }else{
          // altrimenti permutiamo:
          Permutations(level+1,size);
          for(i=level+1; i<size ;++i){
               Swap((letters+level),(letters+i));
               Permutations(level+1,size);
               Swap((letters+level),(letters+i));
          }
     }
}
</FUNCTION>
In breve:
Otteniamo n! stringe tramite una serie di chiamate ricorsive.
supponiamo di avere 3 elementi:
a livello 0 facciamo 3 chiamate
(L0)  una sola chiamata (quella fatta in main).
(L1) 3 chiamate
per ognuna di queste chiamate ne facciamo 2:
(L2) 6 chiamate
ora ognuna di queste 6 chiamate a livello 2 chiameranno 1 sola funzione a
livello 3
(L3) 6 chiamate
ora si verifica la condizione:
if(level==size)
e quindi smettiamo la nostra discesa ricorsiva e.....
Abbiamo 6 chiamate e stampiamo quindi 6 stringhe!
Nota che dal mio esempio sembra che si abbiano 6 chiamate a livello 3
contemporaneamente, cio' non e' vero! Se ne ha una per volta... ma questo
non cambia il concetto!
Il problema in realta' non e' stampare n! stringhe, ma piuttosto stampare
quelle giusto in modo da avere tutte le possibili permutazioni. Per fare
cio' prova di capire come funzione il mio algoritmo e se hai qualche
problema chiedi pure.
Ora vediamo come funziona:
<OUTPUT>
Stringa di partenza: abcd
abcd
abdc
acbd
acdb
adcb
adbc
bacd
badc
bcad
bcda
bdca
bdac
cbad
cbda
cabd
cadb
cdab
cdba
dbca
dbac
dcba
dcab
dacb
dabc
Stringa di arrivo: abcd
Numero di stringhe stampate: 24
</OUTPUT>
ok ora cambiamo 2 righe:
char letters[] = {'a','b','c','d','\0'};
in

 in
ooops scappato una combinazione di tasti... (non ho pututo rileggere e...
nemmeno finire!) sigh....
Bene:
ok ora cambiamo 2 righe:
char letters[] = {'a','b','c','d','\0'};
in
char letters[] = {'a','b','c','\0'};
e
Permutations(0,4);
in
Permutations(0,3);
ed otteniamo:
Stringa di partenza: abc
abc
acb
bac
bca
cba
cab
Stringa di arrivo: abc
Numero di stringhe stampate: 6
come vedi il tutto e' "flessibile"!
Ora, per finire proviamo con :
char letters[] = {'a','b','c','d','e','f','g','h','\0'};
e
Permutations(0,8);
<OUTPUT>
[...MEGA CUT....]
Stringa di arrivo: abcdefgh
Numero di stringhe stampate: 40320
</OUTPUT>
Spero ti sia utile,
Tommy

 ha scritto:

Hai perfettamente ragione. E' sempre una soluzione però. La ricorsione
è un po' più complessa ed avevo 2 minuti di tempo ;-)
Non sono molto amico della complessità computazionale ;-)
Ciao


 Non sono molto amico della complessità computazionale ;-)
Beh, questo e' un tuo problema e tra le altre cose grosso!
A me le cose difficili invece piacciono, me le studio, le imparo e .... beh,
miglioro (se posso). Se invece a te non piacciono le cose che non sai (bene
o per nulla) allora non migliorerai mai (o quasi).
Tommy
N.B. e' piu' che possibile implementare l'algoritmo in modo iterativo ma non
nel modo descritto da te.

nel modo descritto da te.
Anche nel modo descritto da me. Anche in un altro modo. Anche nel modo
descritto da te. Nessuno mi ha chiesto l'algoritmo piùefficente.
Non credo sia bello iniziare a attarci a vicenda, credo che non
sarebbe nemmeno costruttivo. Io mi sono permesso di esprimere la mia
opinione su un tuo atteggiamento. Impressione personale dettata da un
errore di interpretazione, se vuoi. Non credo che per questo tu debba
tirar fuori storie del genere. 


 tirar fuori storie del genere. 
Ti riferisci all'altro messaggio?
Non importa ho gia' risposto a quel messaggio e spero che la questione
sia gia' risolta.
Tommy
P.S.
ho messo # al posto delle tue lettere accentate, andrebbero evitate se
possibile....
Tu ne avevi scritte moltissime, quelle che vedi sono solo quelle che
sono contenute nei pezzi che ho quotato.
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG