Prolog考试复习求助：实现permute/2列表排列谓词

嘿，复习Prolog考试刷往届卷卡壳太正常了！这个生成列表排列的permute/2谓词是经典的递归问题，我来给你一步步讲清楚怎么写：

核心思路 #

排列的本质就是每次从原列表中挑选一个元素作为结果列表的首元素，然后递归生成剩余元素的排列，把这两部分拼起来就是一个完整的排列。

完整实现代码 #

Prolog自带的select/3谓词刚好能帮我们完成“挑选元素+获取剩余列表”的操作，所以可以直接基于它写：

% 基础情况：空列表的排列只能是空列表
permute([], []).

% 递归情况：从Xs中选一个元素Y作为Ys的首元素，再递归排列剩下的元素
permute(Xs, [Y|Ys]) :-
    select(Y, Xs, Rest),  % 从Xs中取出Y，剩下的元素存在Rest里
    permute(Rest, Ys).    % 递归生成Rest的排列，拼在Y后面

测试验证 #

当你查询?- permute([1,2,3], Ys).时，Prolog会回溯遍历所有可能的挑选方式，最终返回6种不同的排列结果，顺序可能和题目里的不完全一致，但所有合法排列都会被覆盖，完全符合题目要求。

如果你没有自带的select/3怎么办？ #

有些极简Prolog环境可能没有内置select/3，那你可以自己实现这个辅助谓词：

% 情况1：要选的元素就是列表的第一个元素
select(Y, [Y|Rest], Rest).

% 情况2：要选的元素在列表后面，递归查找
select(Y, [X|Xs], [X|Rest]) :-
    select(Y, Xs, Rest).

把这段代码和permute/2放在一起，就能正常运行啦～

内容的提问来源于stack exchange，提问作者user9759943