计算序言中列表的排列

在《序言艺术》第二版中有一个问题，您应该定义一个谓词 Even_permutation(Xs,Ys) 和类似的奇数排列，当您查询时，例如 Even_permutation([1,2,3],[2,3, 1]) 和 odd_permutation([1,2,3],[2,1,3]) 为 true。这些谓词应该能够在随机列表上工作并确定该列表的排列是奇数还是偶数位置。我有我的排列谓词，如图所示。

permutation([],[]).
permutation(Xs,[Z|Zs]):-select(Z,Xs,Ys), permutation(Ys,Zs).
select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]):- select(X,Ys,Zs).

我有一个想法，我计算列表的排列数量并将它们分为偶数和奇数排列，然后我的查询可以确定排列是奇数还是偶数，但我不知道如何实现它。如果有更好的方法请告诉我。

我知道原来的问题是很久以前发布的，但我最近正在解决其中的一些问题Prolog 的艺术也思考了几天的偶/奇排列问题。我不想打开重复的问题，所以我在这里发布我的解决方案。

书中提出的问题是：

为以下对象编写程序even_permutation(Xs, Ys) and odd_permutation(Xs, Ys) 发现Ys，分别是偶数和奇数排列， 一个列表的Xs。例如，even_permutation([1,2,3], [2,3,1]) and odd_permutation([1,2,3], [2,1,3])是真的。

所以它需要排列生成器，而不仅仅是验证器。 @hardmath 提供了偶数或奇数排列的正确定义的链接。本书作者举了两个简单的例子来说明。

对我来说，关键是找出偶数或奇数排列的递归定义。对于所有排列，Prolog 中的经典排列生成器使用以下概念：

• N+1 个元素的每个排列都是一个列表，表示 N 个元素的排列，并将第 (N+1) 个元素插入到列表中。

谓词select or insert用于进行插入。

对于偶数和奇数排列，我考虑了类似的想法：

• Every evenN+1 元素的排列是表示一个列表even将第 (N+1) 个元素插入到某个位置的 N 个元素的排列odd列表中的位置，或代表一个列表odd将第 (N+1) 个元素插入到某个位置的 N 个元素的排列even在列表中的位置。

• Every oddN+1 元素的排列是表示一个列表odd将第 (N+1) 个元素插入到某个位置的 N 个元素的排列odd列表中的位置，或代表一个列表even将第 (N+1) 个元素插入到某个位置的 N 个元素的排列even在列表中的位置。

其原理是，在奇数位置插入元素表示相对于原始列表的偶数次交换（列表的前面是第一个位置，不需要交换，因此它是偶数）。类似地，在偶数位置插入元素表示相对于原始列表的奇数次交换。

如果我添加空列表是它自己的偶数排列的规则，那么我可以如下定义以下谓词来生成偶数和奇数排列：

even_permutation( [], [] ).
even_permutation( [X|T], Perm ) :-
    even_permutation( T, Perm1 ),
    insert_odd( X, Perm1, Perm ).
even_permutation( [X|T], Perm ) :-
    odd_permutation( T, Perm1 ),
    insert_even( X, Perm1, Perm ).

odd_permutation( [X|T], Perm ) :-
    odd_permutation( T, Perm1 ),
    insert_odd( X, Perm1, Perm ).
odd_permutation( [X|T], Perm ) :-
    even_permutation( T, Perm1 ),
    insert_even( X, Perm1, Perm ).

insert_odd( X, InList, [X|InList] ).
insert_odd( X, [Y,Z|InList], [Y,Z|OutList] ) :-
    insert_odd( X, InList, OutList ).

insert_even( X, [Y|InList], [Y,X|InList] ).
insert_even( X, [Y,Z|InList], [Y,Z|OutList] ) :-
    insert_even( X, InList, OutList ).