Discussion :

[MysticKhal_0]

Bonjour à tous

Je vais commencer par un exemple je trouve pas vraiment de formulation.

Soit la suite:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Ici on a donc une suite de nombres dans l'ordre lexicographique et telle que chaque nombre contient 1 seule fois les chiffres de 1 à 3.

Le problème est comment obtenir cette liste de façon simple? C'est à dire (si c'est possible) sans dépasser O(K!) avec K la longueur d'un nombre.

Le problème parait assez simple mais pour le moment j'ai pas trouvé d'algo efficace.. (On peut aussi voir le problème comme: "Comment trouver le nombre après 3 1 2 4? en O(1)" par exemple, si ça peut aider quelqu'un :s).

Merci beaucoup

[millie]

"Comment trouver le nombre après 3 1 2 4? en O(1)" par exemple, si ça peut aider quelqu'un :s).

Ce n'est pas possible en O(1), dans le pire ces cas, tu as forcement O(n).

Ce que tu souhaites, c'est simplement générer des permutations de (1,2,3) :

Regarde ici (ce ne sont que les combinaisons) :
http://www.developpez.net/forums/sho...d.php?t=228599
Et notamment le lien suivant qui traite des permutations :
Generating all permutations: http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz

[pseudocode]

Le problème est comment obtenir cette liste de façon simple? C'est à dire (si c'est possible) sans dépasser O(K!) avec K la longueur d'un nombre.

??

Comment construire une liste K! elements en moins de K! opérations ?

P-e avec un ordinateur quantique...

[MysticKhal_0]

Euh non je sous entendais en K! opérations, mais pas en plus (bonne remarque celà dit ).

En cas merci pour vos réponses Y'a donc pas "la permutation qui marche toujours", pas étonnant que je trouvais rien ^^

'Résolu.

[pseudocode]

Euh non je sous entendais en K! opérations, mais pas en plus (bonne remarque celà dit ).

En cas merci pour vos réponses Y'a donc pas "la permutation qui marche toujours", pas étonnant que je trouvais rien ^^

'Résolu.

on doit pouvoir le faire par des rotations imbriqués, mais ca va couter en mémoire.

Groupe de 3 elements (G3): # # # -> 2 rotations successives possibles avant de se retrouver dans l'état inital. Soit 3 positions possibles

Sous groupe des 2 elements de droite (G2): - # # -> 1 rotation possible avant de se retrouver dans l'état inital. Soit 2 positions possibles

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
* Etat initial
1 2 3  G3:position 1/3 et G2:position 1/2 
 
* push (sauvegarde l'etat dans la pile) + rotation G2
1 3 2  G3:position 1/3 et G2:position 2/2
 
* pop (restore le dernier etat sauvé) + rotation G1
2 3 1  G3:position 2/3 et G2:position 1/2
 
* push + rotation G2
2 1 3  G3:position 2/3 et G2:position 2/2
...

[FrancisSourd]

"Comment trouver le nombre après 3 1 2 4? en O(1)" par exemple, si ça peut aider quelqu'un :s).

Cela en tout cas, on peut le faire en O(n).

Soit la permutation p[1] p[2] p[3]... p[n]
(p[1]=3, p[2]=1, p[3]=2, p[4]=4 pour ton exemple).

Tu cherches le plus grand indice i tel que p[i]<p[i+1]
S'il n'y en a pas, cela veut dire que tu es arrivé à la dernière permutation
n (n-1) ... 3 2 1

Ensuite, tu remplaces p[i] par la plus petite valeur p[j] tel que j>i et p[j]>p[i].

Enfin, tu mets dans p[i+1] ... p[n] les valeurs restantes dans l'ordre croissant.

NB: Je dis cela de mémoire, j'espère que je ne dis pas de bétises. Sinon lire Knuth (lien dans les précédents messages)