logo标签列表

单周期置换

prologpermutation
3
让我们来看一个只有一个循环的数字排列 {1,2,3,4}，例如 (2,3,4,1)。我想知道如何使用Prolog生成所有这样的排列。
我知道如何使用 select 生成所有排列。
但我无法想出如何仅生成单个循环的排列。
能否给我一些提示或建议？
给定n个符号，有(n-1)!个由这些符号组成的环形排列。为什么？ - hardmath
阅读关于第一类斯特林数的内容，它计算具有k个不相交循环的n个元素的排列数量。您应该看到递归，并且这应该对您有所帮助，或者我可以为您解释。 - xyz
请不要从Stack Overflow上删除您的问题。有些人花费时间提供好的答案，请尊重他们的工作。 - regilero
4个回答
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).
0

你能否使用生成所有排列的函数，并过滤掉不是“单循环排列”的那些吗？（由于我对“单循环排列”一点也不清楚，所以无法帮助编写该过滤器。）

0

感谢hardmath在答案中的讨论，我终于明白了这是关于什么的。

看起来解决方案很简单，只需将输入列表的尾部替换为其排列，以形成循环描述，然后通过将每个元素与其下一个元素配对并按第一个组件排序来将该描述转换为列表表示，以获取第二个组件的结果列表：

single_cycled_permutation([A|B],   R) :-
  permutation(B,    P),
  cycle_pairs(A, A, P, CP),
  sort(                CP, SCP),
  maplist( pair,           SCP, _, R).

pair( X-Y, X, Y).

cycle_pairs(  A, X, [Y|Z], [X-Y|W]) :-
  cycle_pairs(A, Y,    Z ,      W ).
cycle_pairs(  A, X, [   ], [X-A]  ).

为了更容易地看到循环，请在single_cycled_permutation中删除最后一个目标：

single_cycled_pairs([A|B], SCP) :-
  permutation(B,    P),
  cycle_pairs(A, A, P, CP),
  sort(                CP, SCP).

测试：

21 ?- forall(  single_cycled_pairs([1,2,3,4], SCP), 
               (maplist(pair,SCP,_,R), write((SCP,R)), nl)).
[1-2,2-3,3-4,4-1],[2,3,4,1]
[1-2,2-4,3-1,4-3],[2,4,1,3]
[1-3,2-4,3-2,4-1],[3,4,2,1]
[1-3,2-1,3-4,4-2],[3,1,4,2]
[1-4,2-3,3-1,4-2],[4,3,1,2]
[1-4,2-1,3-2,4-3],[4,1,2,3]
true.

另请参阅：

0
one-cycle([H|T], Permutation) :-
    permutation([H|T], Permutation),
    cycle(H, [H], [H|T], Permutation, Cycle),
    length(Cycle, CycleLength),
    length([H|T], ListLength),
    CycleLength =:= ListLength.

cycle/5 谓词根据您传递的第一个参数构建对应的循环。第二个参数是累加器，初始化为 [FirstArgument]，第三和第四个参数是原始的 List 和 Permutation，最后一个参数是结果（包含循环元素的列表）。

cycle(Current, Acc, List, Permutation, Cycle) :-

调用corresponds/4会检索出排列中第一个参数所占据位置的项目：

    corresponds(Current, List, Permutation, R),

如果这个项目在我们正在构建的循环中，那么这意味着我们已经完成了循环的构建，因此我们将 Cycle 和累加器 (Acc) 统一起来。
    (   member(R, Acc)
     -> Cycle = Acc

如果没有，我们将通过使用找到的相应项递归调用我们的谓词并将其添加到累加器中继续进行，以便我们的构建周期现在包含它：
     ;  cycle(R, [R|Acc], List, Permutation, Cycle)).

corresponds(N, [N|_], [R|_], R) :-
    !.
corresponds(N, [_|L], [_|P], R) :-
    corresponds(N, L, P, R).

用法：

?- one-cycle([1, 2, 3, 4], P).
P = [2, 3, 4, 1] ;
P = [3, 1, 4, 2] ;
P = [3, 4, 2, 1] ;
P = [2, 4, 1, 3] ;
P = [4, 1, 2, 3] ;
P = [4, 3, 1, 2] ;
false.
关于循环和什么是一个周期，您可以在这里阅读：http://en.wikipedia.org/wiki/Permutation。 - xyz
关于算法的内容：我们想要找到一个单周期排列。因此，我们有两个列表 L 和 P。P 是仅有一个循环的 L 的排列。因此，首先我们检查是否正确：permutation(L,P)。然后我们可以看到，L 和 P 的头部不应该是相同的数字。接下来，让我们取 [1,2,3,4] 和 [4,1,2,3]，因此我们注意到如果我们从 L 和 P 中选择头部，那么 2、3、4 不能成为 [1,2,3] 的排列（由于单周期的定义）。 - xyz
我添加了我认为是正确的解决方案，因为现在我终于理解了什么是循环（终于 :( ）。 - m09
我基本上只构建了一个循环，如果这个循环的大小不等于列表的大小，则排列不是一个单循环。你觉得呢？ - m09
它建立了一个循环，以便我们可以将其长度与列表进行比较，因为如果排列是单周期排列，则其任何一个循环（仅有一个偶数）的长度与列表相同... - m09
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接