Algoritmo para permutar

["Ecass Dodebel" <ecassdodebel@xxxxxxxxxxx>]

Olá!

100 = <4020> = 4*4! + 0*3! + 2*2! + 0*1!

E também

4! = <1000>
6! = <100000>
4!-1 = <321>

De modo geral, eu defino:

<a[n]a[n-1]...a[1]> = a[n]*n! + a[n-1]*(n-1)! + ... + a[1]*1!, sendo 
0<=a[i]<=i

Cada número só pode ser representado de um modo. Para quem se interessa por 
algoritmos, eu inventei um para achar rapidamente todas as permutações de n 
elementos, vejam:

São dados n elementos, vou simplificar por {1,2,...,n}. Existem n! 
permutações desses elementos. A k-ésima permutação é feita da seguinte 
maneira:

Algoritmo. tomamos <a[n-1]...a[1]> = k. (achar os a[i] é fácil, similar a 
achar 1, 3 e 5 em 135)
Nós temos n espaços vazios onde vamos colocando os elementos que queremos 
permutar. Começamos da esquerda para direita, a primeira casa é o primeiro 
espaço em branco, e contamos a[k] espaços em branco para a direita, é onde 
colocamos o elemento k+1 (o 1 é posto no espaço que sobrar). Sendo que 
devemos colocar os elementos na ordem n,(n-1),...,1.

Exemplo. Para n=4, queremos descobrir a 15a. permutação k = 15 = 2*6+1*2+1*1 
= <211>, daí usamos o algaritmo e vamos preenchendo os espaços em branco.
XX4X  ( 2 espaços em branco a partir do primeiro )
X34X  ( 1 espaço em branco a partir do primeiro )
X342  ( 1 espaço em branco a partir do primeiro )
1342, e essa é a 15a. permutação

Se variarmos k de 0 até 23, teremos todas as permutações possíveis, 
calculadas de um jeito bem rápido (com o auxílio de um computador).


Obrigado!

Eduardo Casagrande Stabel.


Obs. a ordem das permutações eu inventei
________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com