Newsgroup: it.scienza.informatica
Titolo: permutazioni su n oggetti

Ciao a tutti,c'e'qualcuno che ha un idea su come realizzare un algoritmo (in
pascal oppure in assembler mips) che permetta di generare tutte le 16!
permutazioni su 16 oggetti (numeri)?
Cioč mi interessa un algoritmo che preso in input un numero n compreso tra 1
e 16! mi generi una delle 16!permutazioni possibili.
Se non c'e' un algoritmo mi basta l'idea di base con la quale
partire.Grazie!

permutazioni su 16 oggetti (numeri)?
Spero di non aver capito male :
program Perm16 ;
var a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p : integer ;
begin
  for a := 1 to 16 do
   for b := 1 to 16 do
    for c := 1 to 16 do
     for d := 1 to 16 do
      for e := 1 to 16 do
       for f := 1 to 16 do
        for g := 1 to 16 do
         for h := 1 to 16 do
          for i := 1 to 16 do
           for j := 1 to 16 do
            for k := 1 to 16 do
             for l := 1 to 16 do
              for m := 1 to 16 do
               for n := 1 to 16 do
                for o := 1 to 16 do
                 for p := 1 to 16 do
                   writeln (a:3,b:3,c:3,d:3,e:3,f:3,
                            g:3,h:3,i:3,j:3,k:3,l:3,m:3,n:3,o:3,p:3) ;
end.

io (
anna...@tin.it
) wrote:
: Ciao a tutti,c'e'qualcuno che ha un idea su come realizzare un algoritmo (in
: pascal oppure in assembler mips) che permetta di generare tutte le 16!
: permutazioni su 16 oggetti (numeri)?
: Cioè mi interessa un algoritmo che preso in input un numero n compreso tra 1
: e 16! mi generi una delle 16!permutazioni possibili.
: Se non c'e' un algoritmo mi basta l'idea di base con la quale
: partire.Grazie!
Dovrebbe essere facile, con la ricorsione, intanto chiama gli oggetti 1, 2, 
3, ..., poi crea la funzione permutatione che prende un array come argomento,
e, per ogni elemento dell'array, ad esempio 5, crea tutte le permutazioni
del tipo (5, permutazione(1,2,3,4,6,...,16). I dettagli te li lascio come 
esercizio.

partire.Grazie!
L'idea per generare tutte le possibili permutazioni di n oggetti (che sono
ben n!, quindi tante) e' abbastanza semplice: si trattano gli oggetti da
permutare come componenti di un "paniere". Si prende quindi un "casellario"
grande n e si comincia a prendere il primo oggetto disponibile non ancora
utilizzato nel paniere e a piazzarlo nella prima casella. Si prosegue fino a
riempire tutto il casellario meno l'ultima posizione (nel paniere sara'
rimasto un unico oggetto disponibile) e si e' generata la prima
permutazione. Qui si innesca il backtracking: si svuota l'ultima casella
riempita, si prende l'oggetto successivo a quello che c'era e si continua a
riempire con lo stesso criterio. Come paniere si puo' usare un'array di flag
booleani (true=oggetto disponibile e false oggetto gia' usato in un'altra
casella). Come casellario si puo' usare un array di n interi. Ogni volta che
si riempie una casella si mette a false l'elemento corrispondente del
paniere e si prosegue a riempire il casellario. Quando si innesca il
backtracking si libera la casella, si rimette a true l'elemento del paniere
e lo si sostituisce col prossimo disponibile.
Spero di essere stato chiaro
Ciao
                                           Max
Massimo Sanna                               \
E-mail: 
s78...@athena.polito.it
              \
 
fdr...@cclinf.polito.it
              \
ICQ:    25037591                               \
Home:   
http://www.poli.studenti.to.it/~m.sanna
 \	
-------------------------------------------------
"Vedi Bongo, questo e' il progresso! Hai tutto quello che non vuoi, 
 quando non ti serve". 
                                              A. De Curtis
                ------
               | STOP | <-  "CLICK HERE TO SHUTDOWN"
                ------

 partire.Grazie!
--
--------------------------------------------------------------
Fabrizio Sebastiani, 
http://userspace.ats.it/free/fsebasti
--------------------------------------------------------------

var a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p : integer ;
Si, hai capito male. Coraggio... a veterinaria sono ancora aperte le
iscrizioni :-)) (scherzo, naturalmente!!).


iscrizioni :-)) (scherzo, naturalmente!!).
Ci mancherebbe...
Andrea Laforgia
-----------------------------------------------------
There is nothing better for understanding a kangaroo
than seeing it jump.
-----------------------------------------------------

Ci mancherebbe...
eh... appunto eheh :)