Permutations ML standard

Question

Je travaille sur une fonction aux permutations pour toutes les valeurs d'une liste.

Voici ce que j'ai jusqu'à présent:

//MY ROTATE FUNCTION 

fun rotate e [] = [[e]] 
| rotate e (x::xs)= (e::x::xs)::(List.map (fn l => x::l) (rotate e xs)); 

//MY CURRENT PERMUTATION FUNCTION 

fun perm [] = [] 
| perm (x::xs) = List.concat(List.map (fn l => (rotate x xs)) xs) @ perm xs; 

SORTIE:

- perm [1,2,3]; 

val it = [[1,2,3],[2,1,3],[2,3,1],[1,2,3],[2,1,3],[2,3,1],[2,3],[3,2]] 

La sortie doit être quelque chose comme [[1, 2, 3], [1, 3, 2] , [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]. Comme vous pouvez le voir, il me manque quelque chose ici. Je crois que le problème est mon 3 n'est pas passé à tourner comme rotation 3 [1,2] est ce qui me manque de mon code avec deux listes de 2 éléments étant ici pour une raison quelconque.

Comment puis-je corriger ma fonction perm pour afficher la sortie correctement? Toute aide, quelle que soit sa taille, m'aiderait beaucoup.

Answer 1

Je ne pense pas que l'approche de rotation est celle que vous voulez prendre. Plutôt, comme Shivindap describes here, un bon moyen de faire ce genre de ceci est de tirer le premier élément de la liste d'arguments, et de l'ajouter à toutes les permutations de la queue. Rincez et répétez ceci pour chaque élément de la liste, et vous obtiendrez toutes les permutations. Vous trouverez une explication détaillée de cette approche here. Pour les exemples de code en ML, vous pouvez aussi check this out.

Bonne chance à vous!

Answer 2

Voici une solution simple pour votre solution essayée. Vous étiez presque là.

fun interleave x [] = [[x]] 
| interleave x (h::t) = 
    (x::h::t)::(List.map(fn l => h::l) (interleave x t)) 

fun permute nil = [[]] 
| permute (h::t) = List.concat(List.map (fn l => interleave h l) (permute t))