Newsgroup: it.hobby.enigmi
Titolo: Permutazioni

Saluti a tutti.
È un po' di tempo che cerco una soluzione ad un problema e non sono capace
di trovarla volevo sottoporlo alla vostra attenzione per sentire cosa ne
pensate.
Premetto che non so se questo problema ha soluzioni o meno. Un amico dice
che "potrebbe essere sia banalmente risolvibile sia banalmente impossibile".
Questo è il quesito: esiste una relazione biunivoca tra un numero naturale e
l'ennesima permutazione di n elementi presi n a n. così non si capisce
nulla!  :-)
Vediamo se con un esempio riesco a chiarire il problema.
Quali sono i modi in cui posso disporre tre libri (A B C) uno accanto all'
altro su uno scaffale?
In questo caso la risposta è banale. Sono sei possibili permutazioni (modi
diversi di disporre gli elementi) in altre parole 3! (si legge "tre
fattoriale" ed e uguale a 3*2*1 = 6) e sono banalmente determinabili:
1) A B C
2) A C B
3) B A C
4) B C A
5) C A B
6) C B A
E con 4 libri cosa succede? Le cose si complicano un po' ma ancora si riesce
a dare una risposta, le permutazioni sono 4! = 4*3*2*1 = 24  nel dettaglio:
1)  A B C D
2)  A B D C
3)  A C B D
4)  A C D B
5)  A D B C
6)  A D C B
7)  B A C D
8)  B A D C
9)  B C A D
10) B C D A
11) B D A C
12) B D C A
13) C B A D
14) C B D A
15) C A B D
16) C A D B
17) C D B A
18) C D A B
19) D B A C
20) D B C A
21) D A B C
22) D A C B
23) D C B A
24) D C A B
Capite che aumentando il numero di libri le cose si complicano velocemente.
Con sette elementi le permutazioni diventano 7! = 5040 troppe per la mia
pazienza!
Allora penso che sarebbe carino trovare una "formulina" matematica che mi
dia la risposta.
Con questo no voglio dire che sono in cerca di un algoritmo che mi dia la
risposta in questo modo sono capace, voglio proprio un formula del tipo:
per la permutazione ennesima  n  la disposizione è  A B C.  o  f(n) =
{X,Y,Z. } ;
nel caso di 4 libri la 18 permutazione è C D A B  oppure  f(18) = { C D A
B } .
Tornando alle considerazioni iniziali non sapendo nulla sulla risolvibilità
del quesito è ovvio che la dimostrazione d'irrisolvibilità è una soluzione
possibile.
Buona meditazione a tutti Gianvito Cassinadri

 nulla!  :-)
Il metodo e' facilissimo. Te lo mostro per il caso di 5 elementi,
poi generalizzarlo al caso generico e' banale.
supponiamo di mettere gli elementi in una lista, tanto per
tenerli in un qualche ordine e per poterli numerare.
Quindi supponiamo che gli elementi siano L={a,b,c,d,e}
e quindi n=5, se indico con n il numero degli elementi
Numeriamo le permutationi da 0 a (5!)-1=119  e supponiamo di voler
generare la 82-esima permutazione (in generale la p-esima permutatione
con p che varia tra 0 e (n!)-1.
Ora ripetero' un ciclo di operazioni n volte, una per ogni elemento
della permutaziono che voglio generare (nel nostro caso 5).
Utilizzero' un indice, diciamo k che vale n-1 al primo ciclo
e viene decrementato ad ogni ciclo, di modo che nell'ultimo ciclo
vale 0. Nel nostro caso inizialmente k vale n-1=5-1=4.
Ciclo
--------------
Divido il valore corrente di p per (k+1)! e
assegno a p il valore del resto della divisione.
divido p per k! e se v e' il risultato (intero)
allora emetto l'elemento (v+1)-esimo di L
e lo cancello da L(ricompattando L).
decremento k e se k diventa negativo ho finito.
-------------------------------------
vediamo l'applicazione
1o Ciclo
------------
p vale 82, k vale 4 e L={a,b,c,d,e}.
allora (4+1)!=120. Il resto della divisione
di 82 per 120 e' proprio 82, quindi p rimane
invariato a 82.
v = 82 / (4!) = 3 quindi emetto (come primo
elemento della permutazione) l'elemento
3+1 di L ovvero "d". Cancello "d" da L e quindi
L diventa L={a,b,c,e}.
Decremento k che diventa uguale a 3.
2o Ciclo
----------------
p vale 82, k vale 3 e L={a,b,c,e}.
allora il resto della divisione di p
per (3+1)!=24 e' uguale a 10, quindi p=10.
v = 10 / 3! = 1 quindi emetto l'elemento 1+1 di L
ovvero "b". (la permutazione corrente emessa diventa quindi
"db"). L diventa {a,c,e}.
Decremento k che diventa uguale a 2.
Vado avanti cosi', ricordandomi che 0!=1!=1.
L'ultimo ciclo (quello quando k=0) posso anche non
eseguirlo, poiche' sono arrivato ad avere L composto da
un solo elemento e quindi posso direttamente emetterlo
ed ho finito.
ciao,
g.