prolog - 单周期排列

Question

让我们对数字{1,2,3,4}进行排列，其中只有一个循环。例如，它可以是：（2,3,4,1）。我想知道如何使用Prolog生成所有这样的排列？

我知道如何使用select生成所有排列。

但是我无法提出仅生成一个周期（即单周期）排列的想法。

有人可以给我一个小的提示或建议吗？

Answer 1

我的评论旨在作为直接产生单个周期排列的提示，而不是生成所有排列并过滤掉包含单个周期的排列的提示。

我们也许应该澄清一下，经常使用排列的两种表示形式。 xyz写道“我知道如何生成所有排列”，大概意味着类似我在this 2006 forum post中给出的代码。在这里，所有排列都是根据列表以“标准顺序”列表重新排列项目的方式表示的。

显然有N个！各种排列。其中有多少个是单周期排列？通过考虑对置换有用的另一种形式（即不相交循环的产物），可以轻松地回答该问题。我们需要区分一个像（1,2,3,4）的循环和身份置换[1,2,3,4]。实际上，周期（1,2,3,4）将1映射为2，将2映射为3，将3映射为4，并将4映射为1，所以与其在身份置换中不是[2,3,4,1]其列表表示形式。

现在循环本身循环了，所以我们选择开始循环符号是任意的。例如，如果我们从1开始，则循环由以下N-1个项目的顺序确定。这表明有（N-1）个！组成单个周期的N个事物的排列（长度为N）。因此，我们可以很容易地以周期形式生成所有单个周期排列，然后问题就减少到从该周期形式转换为排列的列表形式。 [请注意，Mog在某种程度上解决了转换的另一个方向：给定一个置换列表，找出该置换中包含的一个循环（并查看其是否完整）。

这是我的代码，用于生成给定“标准订单”列表oneCycle(Identity,Permuted)的所有单周期列表排列：

oneCycle([H|T],P) :-
    permute(T,S),
    oneCycle2permute([H|S],[H|T],P).

permute([ ],[ ]) :- !.
permute(L,[H|T]) :-
    omit(H,L,Z),
    permute(Z,T).

omit(H,[H|T],T).
omit(X,[H|T],[H|Z]) :-
    omit(X,T,Z).

oneCycle2permute(_,[ ],[ ]) :- !.
oneCycle2permute(C,[I|Is],[P|Ps]) :-
    mapCycle(C,I,P),
    oneCycle2permute(C,Is,Ps).

mapCycle([X],X,X) :- !.
mapCycle([H|T],X,Y) :-
    mapCycleAux(H,T,X,Y).

mapCycleAux(Y,[X],X,Y) :- !.
mapCycleAux(X,[Y|_],X,Y) :- !.
mapCycleAux(_,[X,Y|_],X,Y) :- !.
mapCycleAux(H,[_|T],X,Y) :-
    mapCycleAux(H,T,X,Y).