gpt4 book ai didi

prolog - 在 Prolog 中查找置换循环

转载 作者:行者123 更新时间:2023-12-04 05:18:50 25 4
gpt4 key购买 nike

我是 Prolog 世界的新手。我想知道一个排列是否是“一个周期”。

我正在尝试编写一个谓词来从排列中生成循环。这是我的代码(不起作用):

find_next([E|_], [N|_], E, N).

find_next([_|L1], [_|L2], E, N) :-
find_next(L1, L2, E, N).


find_cycle(L1, L2, E, C) :-
append(C, [E], C1),
find_next(L1, L2, E, N),
find_cycle(L1, L2, N, C1).

排列由两个列表表示(例如:[1, 2, 3, 4], [3, 4, 2, 1])。 find_next为元素 (E) 生成下一个循环元素 (N)(例如:E=1, N=3)。 find_cycle从元素 E 开始寻找循环 (C)。

不幸的是,当 find_next 返回与循环 C 的第一个元素相同的 N 时,我不知道如何停止重复。

编辑:一些例子。
find_cycle([1, 2, 3, 4], [3, 4, 2, 1], 1, X).

应该返回:
X = [1, 3, 2, 4];
false.

和:
find_cycle([1, 2, 3, 4], [4, 2, 1, 3], 1, X).

应该返回:
X = [1, 4, 3];
false.

为什么?
它是将置换简单分解为不相交的循环。
让我们分析第二个排列: [1, 2, 3, 4], [4, 2, 1, 3] .
Take first element: 1.
1 goes into 4
4 goes into 3
3 goes into 1
end of cycle.

这种排列不能分解为一个循环(生成的循环长度小于排列长度)。

最佳答案

要找到排列的所有循环:

perm_to_cycles(Perm, NPerm, Cycles):-
perm_struct(Perm, NPerm, PermS),
perm_to_cycles(PermS, [], [], Cycles),
!.

perm_to_cycles([], _, Cycles, Cycles).
%perm_to_cycles([p(Id, Id)|PermS], _, InCycles, Cycles):-
% perm_to_cycles(PermS, [], InCycles, Cycles). % This clause would remove fixed elements
perm_to_cycles([p(Id, Item)|PermS], Cycle, InCycles, Cycles):-
(select(p(Item, NId), PermS, NPermS) ->
perm_to_cycles([p(Item, NId)|NPermS], [Id|Cycle], InCycles, Cycles) ;
(
reverse([Id|Cycle], RCycle),
perm_to_cycles(PermS, [], [RCycle|InCycles], Cycles)
)
).

perm_struct([], [], []).
perm_struct([Item|Perm], [NItem|NPerm], [p(Item, NItem)|PermS]):-
perm_struct(Perm, NPerm, PermS).

注释子句将删除循环列表的固定元素。

要仅获得一个循环排列,您可以将第三个参数限制为一个单元素列表。例如:
?- perm_to_cycles([1, 2, 3, 4], [3, 4, 2, 1], [X]).
X = [1, 3, 2, 4]
?- perm_to_cycles([1, 2, 3, 4], [4, 2, 1, 3], [X]).
false.
?- perm_to_cycles([1, 2, 3, 4], [4, 2, 1, 3], X).
X = X = [[2], [1, 4, 3]].

关于prolog - 在 Prolog 中查找置换循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13917316/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com