当前位置：文江博客话题详情

prolog permutation

单循环排列

发布于 2024-12-23 02:32:20 字数 186 浏览 2 评论 0 原文

让我们看一下数字 {1,2,3,4} 的排列，其中只有一个循环。例如，它可以是：(2,3,4,1)。我想知道如何使用 Prolog 生成所有此类排列？

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

但我无法想出如何仅生成单周期（即单周期）排列的想法。

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

友谊不毕业 2024-12-30 02:32:20

我的评论旨在作为直接生成单循环排列的提示，而不是生成所有排列并过滤掉由单循环组成的排列。

我们或许应该澄清，排列的两种表示形式经常被使用。 xyz 写道“我知道如何生成所有排列”，大概意思类似于我在这篇 2006 年论坛帖子。这里，所有排列都是根据列表重新排列某些“标准顺序”列表中的项目的方式来表示的。

显然有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).

My comment was intended as a hint for producing directly the single cycle permutations, rather than generating all permutations and filtering out the ones that consist of a single cycle.

We should perhaps clarify that two representations of permutations are frequently used. xyz writes "I know how [to] generate all permutation[s]," presumably meaning something like the code I gave in this 2006 forum post. Here all permutations are represented according to the way a list rearranges the items in some "standard order" list.

Obviously there are N! permutations of all kinds. How many of these are single cycle permutations? That question is easily answered by contemplating the other form useful for permutations, namely as a product of disjoint cycles. We need to distinguish between a cycle like (1,2,3,4) and the identity permutation [1,2,3,4]. Indeed the cycle (1,2,3,4) maps 1 to 2, 2 to 3, 3 to 4, and 4 back to 1, so rather than the identity permutation it would be [2,3,4,1] in its list representation.

Now a cycle loops back on itself, so it is arbitrary where we choose to begin the cycle notation. If we start at 1, for example, then the cycle is determined by the ordering of the following N-1 items. This shows there are (N-1)! permutations of N things that form a single cycle (necessarily of length N). Thus we can generate all single cycle permutations in cycle form easily enough, and the problem then reduces to converting from that cycle form to the list form of a permutation. [Note that in part Mog tackled the conversion going in the other direction: given a permutation as list, ferret out a cycle contained in that permutation (and see if it is full length).]

Here's my code for generating all the one-cycle list permutations of a given "standard order" list, 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 原文

谁的年少不轻狂 2024-12-30 02:32:20

您不能使用该函数生成所有排列，并过滤掉不是“单循环排列”的排列吗？（因为我根本不清楚什么是“单周期排列”，所以恐怕我无法帮助编写该过滤器。）

回复收藏 0 原文

你在我安 2024-12-30 02:32:20

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.

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.

The cycle/5 predicate builds the cycle corresponding to the first argument you pass it. the second argument is an accumulator, initialized to [FirstArgument], the third and fourth one are the original List and Permutation, the last one is the result (the list containing the elements of the cycle).

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

The call to corresponds/4 retrieves the item that took the place of the first argument in the permutation :

    corresponds(Current, List, Permutation, R),

If this item is in the cycle we're building, it means we're done building the cycle, so we unify Cycle and the accumulator (Acc).

    (   member(R, Acc)
     -> Cycle = Acc

If not, we go on by calling recursively our predicate with the corresponding item we found and we add it to the accumulator, so that our building cycle now holds it :

     ;  cycle(R, [R|Acc], List, Permutation, Cycle)).

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

Usage :

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

回复收藏 0 原文

注定孤独终老 2024-12-30 02:32:20

感谢答案中我能够理解它的全部内容。

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

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]
真的。

另请参阅：

Thanks to the discussion in the answer by hardmath I was able to understand what it was all about.

It seems the solution is quite simply to replace the input list's tail with its permutation to form a cycle description, then transform that into its list representation by paring up each element with its next and sorting on the first component to get the list of the second components as the result list:

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

To easier see the cycles simply remove the last goal in single_cycled_permutation:

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

Testing:

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.