如何在不使用 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

我们的想法是生成排列并测试您是否已经创建了这个排列。我正在使用内置谓词 permutation/2.

perm(Ori,Out):-
    perm(Ori,[],Out).

perm(Ori,Acc,Ret):-
    permutation(Ori,Perm),
    \+ member(Perm,Acc),
    !,
    perm(Ori,[Perm|Acc],Ret).
perm(_,L,L).

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

该代码不是最快的代码，因为它会多次检查成员资格。

Answer 2

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

取一个元素 X 并在原始列表中创建没有它的排列 Ys1。
添加此元素 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

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

How to create a list without using findall? Prolog

prolog