Newsgroup: it.comp.programmare
Titolo: permutazioni iterative

Qualcuno conosce un algoritmo *iterativo* per calcolare
le permutazioni di un array (di caratteri o interi)?
La soluzione ricorsiva e' quella classica riportata
su molti testi... ma il procedimento iterativo che
conduce all'elencazione delle permutazioni non lo
riesco ad estrapolare.
grazie x eventuali suggerimenti!

 ha scritto nel messaggio
news:M0H5d.9934$N45.2...@twister2.libero.it...

E' un semplice calcolo matematico che trovi in qualunque testo di calcolo
delle probabilità.
a=[a1,a2,a,3,...,an]
P(a)=n!
Il fattoriale,con un procedimento iterativo,lo calcoli così:
int n=10;
int m=n;
int ris=1;
while (m>1){
    ris=ris*m;
    m--;
}

non voglio sapere *quante* permutazioni si possono
fare di una assegnata sequenza di n elementi...
i muri sanno che sono n!
voglio sapere come GENERARE le n! sequenze servendomi di
una procedura iterativa e non della (classica) soluzione
ricorsiva che viene spiegata e riportata sui
testi di programmazione!
il mio problema e' capire se esiste una *modalita'*
per elencare le permutazioni in modo certo,
senza incorrere in ripetizioni.

posta la soluzione ricorsiva.

 ha scritto nel messaggio
news:g466d.11727$H11.3...@twister1.libero.it...

quella che ti ho proposto non è forse una procedura iterativa?

...

Il metodo che conosco io, si basa sulla creazione di una
matrice in cui ogni riga corrisponde a una delle possibili
permutazioni dell'insieme { 1,2,...n }; la matrice avrà quindi
n! rige e n colonne.
La prima riga corrisponde alla permutazione ordinata, 1 2 ... n.
Al passo generico, si ottiene la permutazione in riga i+1 da quella
in riga i.
Bisogna trovare l'ultimo elemento, chiamalo x, a partire dal 
quale la riga i è ordinata in maniera decrescente. 
Se questo elemento è in posizione 0, allora si è terminato. 
Vuol dire,infatti, che si è passati dalla permutazione iniziale
{ 1, 2,... n } a quella finale { n, n-1, ...1 }, passando prima 
per tutte quelle "intermedie".
Altrimenti, la riga i+1 della matrice è ottenuta nel seguente modo:
  1) si trova nella riga i un elemento y che sia il minore tra
     tutti quelli maggiori dell'elemento di indice ix-1 
     ( ix= indice di x )
  2) si copiano tutti gli elementi fino a ix -1 escluso, nella
     riga i+1
  3) si copia x nella riga i+1
  4) i restanti numeri ( che sono decrescenti ) vengono disposti
     in maniera crescente nella riga i+1
  5) si sostituisce l'elemento con indice ix-1 con y ( sempre 
     nella riga i+1) (*)
  (*) A questo punto l'elemento con indice ix-1 e quello con
      indice iy sono stati scambiati di posto. Il modo in cui 
      è stato scelto y al punto 1, garantisce che lo scambio 
      non modifichi l'ordinamento.
Ripetendo queste operazioni su ogni riga, generi tutte le 
permutazioni dell'insieme { 1, 2.....n }. Usando quest'ultime
come indici, puoi stampare l'array.
Esempio:
array: [ a ][ b ][ c ]
 
perm_1 : 1,2,3  --> stampi [ a ] [ b ] [ c ]
perm_2 : 1,3,2  --> stampi [ a ] [ c ] [ b ]
......
......
......
perm_6:  3,2,1  --> stampi [ c ] [ b ] [ a ]    
Passiamo ora all'algoritmo completo. Nota che è abbastanza laborioso
da scrivere ed è facilissimo sbagliarsi con gli indici.
Sicuramente la soluzione ricorsiva è decisamente più ELEGANTE e,
soprattutto, MOLTO PIU'COMODA. 
Ciao, 
Andrea
// Inizio 
#include <stdio.h>
#include <stdlib.h>
void Print_row ( const char *s, int n, const int *p )
{
     int i=0;
     for ( ; i<n; i++ ) printf ( "%c", s[ p[ i ]-1 ] );
     printf ("\n");
}
int Fatt ( int n )
{
    int fct= 1;
    while ( n>1 ) fct *= n--;
    return fct;
}
void Perm( const char *s, int n )
{
     int i=0, k, num_perm;
     int **perm=NULL;
     int ix, iy;
     /* numero di righe della tabella */
     num_perm= Fatt ( n );
 
 
     /* allocazione memoria per la tabella */
     while ( i<num_perm ) perm[ i++ ]= malloc ( n * sizeof ( int ) );
 
     /* prima riga trattata a parte, inizializzata con la permutazione
        1 2 .... n e stampata */
     for ( i = 0; i < n; i++ ) perm[ 0 ][ i ] = i + 1;
     Print_row ( s, n, perm[ 0 ] );
 
     /* riempie le rimanenti n! - 1  righe */
     for ( k = 1; k < num_perm; k++ )
     {
           /* trova l'elemento x ( indice ix ) nella riga k - 1; 
              x  è l'elemento a partire dal quale perm[ k-1 ] è 
              ordinata in maniera decrescente */
           ix = n - 1;
           while ( ix > 0 && perm[ k - 1 ][ ix - 1 ] >
                   perm[ k - 1 ][ ix ] ) ix--;
 
           /* determina il minimo tra tutti gli elementi maggiori di 
              P[ix - 1]  */
           iy = ix;
           for ( i = ix + 1; i < n; i++ )
	         if (  ( perm[ k - 1][ i ] > perm[ k - 1 ][ ix - 1 ] ) &&
                       ( perm[ k - 1][ i ] < perm[ k - 1][ iy ] )
                     )  iy = i;
           /* copia tutta la parte di perm[ k-1 ] fino a ix - 1 
              escluso */
	   for (  i = 0; i < ix - 1; i++ ) 
                  perm[ k ][ i ] = perm[ k - 1 ][ i ];
           /* inverte la striscia da ix alla fine, eliminando P[iy] e
              inserendo P[ix - 1] al suo posto */
           for (  i = ix; i < n; i++ )
                  perm[ k ][ n - 1 - ( i - ix ) ] =perm[ k - 1 ][ i ];
           perm[ k ][ ix - 1 ] = perm[ k - 1 ][ iy ];
           perm[ k ][ n - 1 - ( iy - ix ) ] = perm[ k - 1 ][ ix - 1 ];
           /* stampa la singola riga */
           Print_row( s, n, perm[ k ] );
      }
}
//fine
Nel main:
 
char s[ 100 ];
scanf ( "%s", s );
Perm( s, strlen( s ) );

Come al solito ho dimenticato un piccolo particolare; peccato che senza
di esso, il programma difficilmente potrebbe funzionare in ambiente Unix. 
Ho scritto e provato il programma su Windows e la dichiarazione/istruzione 
sotto non creavano problemi:
int **perm=NULL;
p[ i ]= ........ 
Subito dopo  < num_perm = Fatt ( n ); > e' meglio però aggiungere: 
perm = malloc ( num_perm * sizeof ( int * ) );
Tutto il resto rimane invariato.
Ciao,
Andrea


Io ne conoscevo uno molto semplice da sviluppare, e si basa sulla 
corrispondenza tra la rappresentazione binaria del numero intero N, e 
gli elementi di un insieme di N elementi.
Ad esempio, considera l'insieme S={a,b,c} con N=3
Se codifico in binario tutti i numeri da 0 a 2^3, ottengo 2^3 
combinazioni, cioč 8 configurazioni binarie
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Cosa ci faccio con questi numeri ? Semplice, li associo all'insieme S in 
questo modo: 0 indica che l'elemento dell'insieme S non deve essere 
preso, 1 indica che l'elemento nell'insieme S deve essere preso. Quale 
elemento dell'insieme S? Semplice, quello che corrisponde alla posizione 
della cifra binaria.
Ad esempio 0 0 0 corrisponde all'insieme vuoto, perchč 0 in prima 
posizione indica che non devo prendere il primo elemento di S, 0 in 
seconda posizione indica che non devo prendere il secondo elemento di S, 
e 0 in terza posizione indica che non devo prendere il terzo elemento di S.
Invece, al contrario 1 1 1 corrisponde all'insieme S, perchč 1 in prima 
posizione indica che devo prendere il primo elemento di S, poi 1 in 
seconda posizione indica che devo prendere il secondo elemento di S, e 0 
in terza posizione indica che devo prendere il terzo elemento di S.
Se considero 1 0 1, corrisponde all'insieme {a,c}, semplice, no?
Spero di essere stato chiaro.
Franz