Стандартные перестановки ML

Question

Я работаю над функцией перестановок для всех значений в списке.

Вот что у меня есть:

//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;

ВЫВОД:

- 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]]

На выходе должно быть что-то вроде [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]. Как видите, я что-то здесь упускаю. Я считаю, что проблема в том, что мои 3 не передаются для поворота, так как поворот 3 [1,2] - это то, чего мне не хватает в моем коде, а два списка элементов здесь присутствуют по какой-то причине.

Как я могу исправить свою функцию perm, чтобы правильно отобразить вывод? Любая помощь, неважно, большая она или маленькая, очень мне поможет.

Answer 1

Вот простое исправление для вашей попытки решения.Вы были почти там.

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))

Answer 2

Я не думаю, что подход с вращением - это тот, который вы захотите использовать.Скорее, как Shivindap описывает здесь , хороший способ сделать это - извлечь первый элемент из списка аргументов и добавить его ко всем перестановкам хвоста. Промойте и повторите это для каждого элемента списка, и вы получите все перестановки.

Здесь вы найдете подробное объяснение этого подхода здесь .Для примеров кода в ML вы также можете проверить это .

Удачи вам!