Пролог рекурсивного перетасовки

Question

Подготовка к экзамену по прологу и проработка прошлых работ, на которые у нас нет ответов, и я застрял на полпути к проблеме, и я действительно надеялся на некоторую помощь!

Вопрос: Напишите предикат permute(Xs, Ys), который скремблирует элементы списка Xs, чтобы получить скремблированный список Ys.

Запрос ?- permute([1,2,3], Ys). должен выполнить шесть раз и дать следующие ответы:

Ys = [1,2,3]
Ys = [2,1,3]
Ys = [2,3,1]
Ys = [1,3,2]
Ys = [3,1,2]
Ys = [3,2,1]

хотя и не обязательно в таком порядке.

Нам рекомендуется использовать предикат, который мы уже сделали, и до сих пор у меня есть это:

insert([], Y, [Y]).
insert([H|T], Y, [Y, H|T]).
insert([H|T], Y, [H|T2]) :- insert(T, Y, T2).

permute([], []).
permute([H|T], X) :- insert(T, H, X).

Когда я запрашиваю его, я получаю только половину того, что должен, и не могу изменить порядок списка.

?- permute([1,2,3], Ys).
Ys = [1,2,3],
Ys = [2,1,3],
Ys = [2,3,1].

Любой совет с благодарностью!

Answer 1

Просто для удовольствия, вот решение, полностью основанное на append/3:

permute(XX, [B|YY]) :-
    append(AA,[B|CC],XX),  % remove random element B from XX
    append(AA,CC,DD),      % DD is XX without B
    permute(DD,YY).        % permute DD into YY
permute([],[]).

Простой для понимания, но, вероятно, менее эффективный, чем традиционная реализация (хотя принцип работы точно такой же; прочитайте комментарии), который уже был предложен.