prolog - 如何在不使用 findall 的情况下创建列表？序言

Question

我正在生成排列:

takeout(X,[X|T],T).
takeout(X,[F|R],[F|S]):-
    takeout(X,R,S).

perm([],[]).
perm([X|Y],Z):-
    perm(Y,W),
    takeout(X,Z,W).

我想知道如何在不使用 findall 的情况下创建所有排列的列表。

示例:

?-perm([1,2,3],List).
List = [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]

Answer 1

按其开头的元素对排列进行分组。

1. 获取一个元素 X 并创建排列 Ys1，但原始列表中不包含该元素。
2. 添加此元素 X 作为所有这些排列的第一个元素，我们就得到了以 X 开头的排列列表 XP。 附加所有组将为您提供所有排列。

cons(X, Xs, [X|Xs]).
perm([], [[]]).
perm(Xs, Ys) :-
    dif(Xs, []),
    maplist({Xs}/[X, XP]>>(select(X, Xs, Xs1),
                           perm(Xs1, Ys1),
                           maplist(cons(X), Ys1, XP)),
            Xs, Yss),
    append(Yss, Ys).

?- perm([1, 2, 3], X).
X = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] ;
false.
?- length(Y, 8), perm(Y, X), length(X, N). %8 factorial
N = 40320