Newsgroup: it.comp.lang.c
Titolo: Permutazioni (?)

Supponiamo io abbia 3 numeri. 1, 2, 3
e voglia far stampare a video tutte le possibili permutazioni, quindi:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
So' che la formula per sapere quanti permutazioni avrò dati n numero è n!
(n fattoriale).
Il problema è che il precedente "esercizio" deve essere svolto per 6
numeri..... quindi 6!= 720 permutazioni.
Avrei bisogno che qualcuno mi desse l'idea di fondo per sviluppare
l'algoritmo ..quindi non è che abbia bisogno dell'implementazione in C ma è
proprio l'idea che mi manca :(
Sicuramente poi avrò difficoltà anche con l'implementazione ma intanto
iniziamo con un ostacolo alla volta :-P
Grazie a tutti
Shaden
P.s. Possibilmente senza usare alberi,grafi,liste o diavolerie del genere :P
...al max con vettori o matrici ;-)

 iniziamo con un ostacolo alla volta :-P
Il modo piu' semplice per risolvere l'esercizio e' usare la ricorsione.
Come hai detto tu il numero delle permutazioni e' n!, usa questo dato per
fare la ricorsione in modo giusto....
Ad esempio se hai 4 numeri la prima chiamata ricorsiva generera' 4 chiamate
ricorsive, ognuna di queste ne generera' 3, ognuna di queste 2, ed ognuna di
queste solo 1. In quest'ultima tu puoi stampare i numeri.
In questo modo sei sicuro di avere 4*3*2*1=24 stampe di numeri. n! = 24
quindi tutto ok.
In pratica con la ricorsione generi un albero, il nodo dell'albero e' la tua
chiamata prima chiamata che avra' 4 figli, ognuno di questi ne avra' 3, poi
ognuno dei figli di quest'ultimo 2 etc.... Contando le foglie (nodi
terminali)di tale albero noterai che sono 24.
Ora le semplici chiamate ricorsive non bastano, dovrai utilizzare uno Swap
per cambiare ogni volta di poco alla volta il tuo array..... Ma a questo
punto che sai come partire non dovrebbe essere difficile capire come e cosa
fare, se non ti viene prova pure anche per tentativi e quando non funziona
usa matita e foglio, segui il percorso dell'algoritmo e prova di capire
perche'.
Tommy

Mi è capitata quest'anno un'esercitazione simile a quello che serve a te...
la allego qui, l'ho implementato in maniera iterattiva (odio le ricorsioni
:))
la cosa carina del mio codice è che puoi usare anche una base maggiore di
10, infatti usa anche le lettere :)
Ciao
Gnagno
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//prototipi delle funzioni che ho utilizzato nel programma
void stampa(int*,char* ,int);   //funzione che stampa il numero
void incrementa(int*,int, int);  //funzione che incrementa il mio numero
main()
{
 int base,ndati,i;
 char *b;   //vettore che contiene la base
 int *num;
 double n;
 printf("Strutture dati\n\tEsercitazione 2\n\tUn sistema di
numerazione\n\n\n");
 do
 {
  printf("inserire la base>=2: ");
  scanf("%d",&base);
 }
 while(base<2);
 b = (char *)malloc(base*sizeof(char)); //creo il vettore della dimensione
adatta a contenere la base
 //metto nel vettore i caratteri corrispondenti agli elementi della base
 for(i=0;i<base;i++)
  if(i<10)
   b[i]=(char)(i+48);  //qui ci sono i numeri (faccio il cast per evitare il
warning)
   else
    b[i]=(char)(i+87);  //qui ci sono le lettere (faccio il cast per evitare
il warning)
 do
 {
  printf("inserire il numero di cifre che compongono ogni numero: ");
  scanf("%d",&ndati);
 }
 while(ndati<1);
 //creo un vettore per rappresentare i numeri
 num = (int *)malloc(ndati*sizeof(int));
 //calcolo il numero di elementi che dovrò rappresentare
 n=pow((double)base,(double)ndati);
 for(i=0;i<ndati;i++)
  num[i]=0;
 //stampo il primo numero
 printf("  0: ");
 stampa(num,b,ndati);
 //stampo tutti gli altri numeri
 for(double j=0;j<n-1;j++)
  {
    printf("%3.0f: ", j+1);
    incrementa(num,ndati,base);
      stampa(num,b,ndati);
   }
 printf("\n\nArrivederci e grazie!");
 fflush(stdin);
 getchar();
}
/*funzione che stampa ogni numero*/
void stampa(int *num,char *base,int ndati)
{
   int i,n;
   for(i=ndati-1;i>=0;i--)
    {
      n=num[i];
    printf("%c",base[n]);
      }
   printf("\n");
}
/*funzione che incrementa ogni numero*/
void incrementa(int *num,int ndati, int base)
{
 int i=0;
   num[i]++;
   while(num[i]==base && i<ndati)
   {
    num[i+1]++;
      num[i]=0;
      i++;
   }
}

Vi Ringrazio per l'aiuto!
Vedrň di risolvere da solo il problema.... alle brutte guarderň il codice
:-P
Perň ci terrei a implementarlo ricorsivamente come suggerisce Tommy ;)
Thaaanks!
Shaden

 una base maggiore di 10, infatti usa anche le lettere :)
Beh, non calcoli le permutazioni...
inserendo 123 dovresti ottenere:
123 132 213 231 312 321
invece il tuo programma stampa:
000 001 002 003 010 011 012 013 020 021 022 023 030 031 032 033 100 101 102
103 110 111 112  113  120 121 122 123 130 131 132 133 200 201 202 203 210
211 212 213 220 221 222 223 230 231  232 233 300 301 302 303 310 311 312 313
320 321 322 323 330 331 332 333
In pratica il tuo programma fa un cosa *moooolto* diversa... conta data una
certa base.
Se dai base 10, conta come siamo abituati, da 0 a 9 o da 0 a 99 o ancora da
0 a 9999999 dipende quanto gli chiedi. Se metti base 2 con 4 cifre conta da
0000 a 1111, ma *conta*.
Questo e' molto diverso da una permutazione.
Quello che fai si fa un semplice ciclo in effetti la ricorsione e' inutile!
Tommy

 odio le ricorsioni
Iterativa, una 't' sola....
Tommy

Però ci terrei a implementarlo ricorsivamente come suggerisce Tommy ;)
Un sistema e' questo; scrivi una funzione che stampa un vettore
lungo M permutando in tutti i modi possibili i primi N elementi
usando questa struttura
   se N==1
     stampi e basta
   altrimenti
     per ciascuno dei primi N elementi
        scambi l'elemento con l'N-esimo
        chiami ricorsivamente la stampa chiendendo di
        permutare solo i primi N-1 elementi
        rimetti gli elementi a posto
Per permutare tutto un vettore basta chiamare la funzione
con N=M
HTH
Andrea