在序言中對列表進行計數

Question

在序言藝術第2版中存在一個問題，您應該在其中定義謂詞even_permutation（Xs，Ys）和類似奇數的排列，當您查詢even_permutation（[1， 2,3]，[2,3,1]）和odd_permutation（[1,2,3]，[2,1,3]）爲真。這些謂詞應該能夠在隨機列表上工作，該清單的排列處於奇數或偶數位置。如圖所示，我有我的謂詞。

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). 

我有一個想法，我算表和他們組的排列數爲奇數和偶數排列，然後我的查詢可以確定permutaion是奇數還是偶數，但我不知道如何實現它。如果有更好的方法去做，請告訴我。

Answer 1

下面是如何確定置換是偶數還是奇數的高級描述，in the usual sense of the terms。

將置換轉換爲不相交週期的乘積。置換的奇偶性是其因素的奇偶性的總和（偶數偶數偶數偶數偶數偶數偶數偶數偶數偶數偶數偶數偶數次數）。奇數長度的週期是偶數排列，偶數長度的週期是奇數排列。例如，長度爲1的循環是身份置換，因此（表示爲轉置的空產品）是偶數置換。

查找不相交週期表示的乘積可以在您的設置中完成，方法是從第一個列表中選擇一個項目，查找第二個列表中相應位置的映射位置，然後用每個圖像的重複查找後續項目，直到循環返回到第一個列表開始處的項目。連續圖像的列表將與不在列表中的項目的軌道不相交，因此認爲它們被消除，並且開始尋找下一個不相交的週期，其中第一個列表的第一個項目還沒有被消除。最終，第一個列表中的所有項目都將被刪除，並已被合併到一個或另一個構建的循環中。

在上面鏈接的文章中描述了確定給定排列的奇偶性的其他方法。如果你真的只想枚舉偶數排列（僅僅是奇數排列），一種方法是修改the enumeration of all permutations，只返回相同奇偶性的排列（參見該章節和後面的章節）。

Answer 2

我知道原來的問題是很早以前發佈的，但是我最近剛剛通過Prolog的一些問題解決了一些問題，並考慮了偶數/奇數置換問題幾天。我不想打開重複的問題，所以我在這裏發佈我的解決方案。

書中的問題問：爲even_permutation(Xs, Ys)和

編寫程序odd_permutation(Xs, Ys)是找到Ys，奇數和偶數排列，分別 列表Xs的。例如，even_permutation([1,2,3], [2,3,1])和 odd_permutation([1,2,3], [2,1,3])是正確的。

所以它要求排列生成器，而不僅僅是驗證者。 @hardmath提供了一個正確定義偶數或奇數排列的鏈接。本書的作者給出了兩個簡單的例子來說明。

對我來說，關鍵是找出一個偶數或奇數排列的遞歸定義。對於所有的置換，在Prolog中經典置換生成器使用了以下概念：

• N + 1個元素的每一個的置換是表示N的元素與（N + 1）插入到元件的排列的列表列表。

謂詞select或insert用於插入。

對於偶數和奇數排列，我認爲是類似的想法：

• 每甚至置換N + 1種元素的或者是表示甚至置換N個與所述元素列表在第（N + 1）個元素處插入的第（N + 1）個元素，或者在列表中的位置處插入的第（N + 1）名單。

• 每奇數置換N + 1種元素的要麼是表示與在列表中的一個奇數位置插入第（N + 1）個元素的奇數置換N的元素的列表，或者表示在列表中的位置甚至處插入具有第（N + 1）個元素的N個元素的排列的甚至列表。

合理的是，一個元件中的奇數位置的插入表示相對於原始列表（該列表的前部，與所述第一位置的偶數個互換的，不需要互換，所以它甚至）。類似地，元素在偶數位置的插入表示相對於原始列表的奇數次交換。

如果我加入到這個規則，即空列表是它自己的，甚至置換，然後我可以定義下列謂詞如下生成奇數和偶數排列：

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).