如果以前的解决方案不满足某些条件，如何尝试新的排列？
How to try new permutations if previous solutions did not meet some conditions?
所以，这是我一段时间以来一直试图解决的练习。我得到一个像这样的输入列表 [a-b,b-c]，它们是节点和连接节点的弧。条件是：
节点需要关联一个唯一编号，从1到N，
并且弧线需要关联一个唯一的数字，从 1 到 N-1，并且该数字必须是减去弧线连接的节点的结果。
所以答案是：
EnumNodos = [enum(3,a), enum(1,b), enum(2,c)],
EnumArcos = [enum(2,a‐b), enum(1,b‐c)]
因此，由于我无法为此提出算法，我也不知道是否有算法，我想，我可以尝试每一种可能性，因为我知道如果输入是正确的，这样我迟早会得到它。
我找到了一个 prolog 排列的例子，如果我给它一些输入列表，它会给出它的排列。然后（在控制台中），如果我点击';'它给了我另一个，依此类推。我正在尝试自己包含该代码。
我还没有完成，但我会提供一些帮助，特别是我尝试排列选项的 "looping" 方法。我真的不知道你会怎么说，在序言中，如果这个动作失败了，尝试另一个新的排列，不同于之前尝试过的每个排列（没有给出';'作为解决方案的输入。因为有很多排列正在进行失败，我想检查它是否失败，如果失败，请尝试另一个。
EDIT 所以我刚刚发现了 setof... 我一直在尝试，但我认为我仍然缺少一个关键部分。截至目前，我觉得我可以获得我需要的所有可能性的列表：setof(Out,perm(ListaEnum, SalidaPerm),X),
但我仍然无法接受失败然后重试的想法。到目前为止我的想法是：我得到 X 结果，然后像处理任何列表一样移动它。我检查它是否有唯一编号等等，如果没有，我想继续沿着那个 X 行驶。所以我将致力于失败而不是成功？？我应该这样做吗？？
% enumerate(CONNECTIONS_IN, NODES_OUT, ARCS_OUT)
%TODO query example of call: enumerate([a-b,b-c], EnumNodos, EnumArcos).
enumerate(C, EnumNodos, EnumArcos) :-
enum_nodes(C, [], NodeListUnique, [], PermNodes, 1),
loopPerm(C, NodeListUnique, EnumArcos, PermNodes, SalidaPerm).
% enum_nodes(CONNECTIONS_IN, NODES_IN, NODES_OUT, IDS_IN, IDS_OUT, START_ID)
% Fills up NODES_OUT with unique nodes, and PERMOUT with IDS. New IDs start at START_ID...
enum_nodes([], N, N, M, M, _).
enum_nodes([A-B | T], N, NOUT, M, PERMOUT, ID) :-
ensure_node(A, N, NTMP1, M, PERMNODESOUTA, ID, ID1),
ensure_node(B, NTMP1, NTMP2, PERMNODESOUTA, PERMNODESOUTB, ID1, ID2),
enum_nodes(T, NTMP2, NOUT, PERMNODESOUTB, PERMOUT, ID2).
% ensure_node(NODE, NODES_IN, NODES_OUT,IDS_IN, IDS_OUT, ID_IN, ID_OUT)
% Adds enum(ID_IN, NODE) to NODES_IN to produce NODES_OUT if NODE does not already exist in NODES_IN
ensure_node(NODE, NODES_IN, NODES_IN, PermNodesNOVALENin, PermNodesNOVALENin, ID, ID) :-
member(NODE, NODES_IN), !.
ensure_node(NODE, NODES_IN, [NODE | NODES_IN], PERMIN, [ID_IN|PERMIN], ID_IN, ID_OUT) :-
ID_OUT is ID_IN + 1.
%At this point I have a list of unique nodes and a list of IDs for said nodes, and I want to start calculatin permutations of this two lists until I find one that works.
loopPerm(C, NodeListUnique, EnumArcos, PermNodes, SalidaPerm):-
crearEnum(NodeListUnique, PermNodes, ListaEnum),
perm(ListaEnum, SalidaPerm),
create_arcs(C, SalidaPerm, []),
%%here is where code stops working properly
loopPerm(C, EnumNodos, EnumArcos, PermNodes, SalidaPerm).
%crear_enum(NODES_IN, IDS_IN, enumLISTout)
%creates a list of enums to be permuted, TODO the idea here is that each call will change the list, so if it failed before, it should try a new one.
crearEnum([], [], []).
crearEnum([H1 | NodeListUnique], [H2| PermNodes], [enum(H2,H1)|Salida]):-
crearEnum(NodeListUnique, PermNodes, Salida).
% create_arcs(CONNECTIONS_IN, NODES_IN, ARCS_OUT).
% Create arcs - makes a list of arc(NODE_ID_1, NODE_ID_2)...
create_arcs([], _, _).
create_arcs([A-B | T], NODES, LISTARCS) :-
ensure_arcs(A,B,NODES, LISTARCS, LISTARCS2),
create_arcs(T, NODES, LISTARCS2).
%ensure_arcs(NODE_A, NODE_B, NODELIST, LISTARCSIN, LISTARCSOUT)
%builds a list of arcs TODO works WRONG when arc already was in the input. It should fail, but it just checks that is a member and moves on. So basically it works when arcs are new, because they are added properly, but not when arcs were already found (and as per the exercise it should fail and try another permutation).
ensure_arcs(A,B,NODES, LISTARCSIN, LISTARCSIN):-
member(enum(NODE_ID_A, A), NODES),
member(enum(NODE_ID_B, B), NODES),
REMAINDER is abs(NODE_ID_A-NODE_ID_B),
member(enum(REMAINDER,_), LISTARCSIN), !.
ensure_arcs(A,B,NODES, LISTARCSIN,[enum(REMAINDER, A-B) | LISTARCSIN]):-
member(enum(NODE_ID_A, A), NODES),
member(enum(NODE_ID_B, B), NODES),
REMAINDER is abs(NODE_ID_A-NODE_ID_B).
perm([H|T], Perm) :-
perm(T, SP),
insert(H, SP, Perm).
perm([], []).
insert(X, T, [X|T]).
insert(X, [H|T], [H|NT]) :-
insert(X, T, NT).
以下是我手工制作的其他一些示例，以备不时之需。我也想道歉，因为我对代码一点也不满意，只是我需要继续前进而不是修复我确定是痛苦的错误（但我真的无法修复，截至现在，我花了太长时间才能获得任何有效的代码，即使勉强也是如此）。
6a
5 4
1b 2e
2 3
3c 5f
1
4d
EnumNodos = [enum(6,a), enum(1,b), enum(2,e), enum(3,c), enum(5,f), enum(4,d)],
EnumArcos = [enum(5,a‐b), enum(4,a-e), enum(3,e-f), , enum(2,b-c), enum(1,c-d)]
5a
4 3
1b 2e
1 2
3c 4f
EnumNodos = [enum(5,a), enum(1,b), enum(2,e), enum(3,c), enum(4,f)],
EnumArcos = [enum(4,a‐b), enum(3,a-e), enum(1,b-c), , enum(2,e-f)]
5a
4 3
1b 2e
2
3c
1
4d
简短的回答是你想做的正是 Prolog 自动所做的：它被称为回溯并且意味着 Prolog会尝试每一种可能性，直到他们都筋疲力尽。
因此，对于您的情况，您可以在概念上将整个任务表述为：
solution(S) :-
candidate(S),
satisfies_all_constraints(S).
就是这样。 Prolog 将生成所有候选解决方案并准确报告那些 "satisfy all constraints"，这是您需要在 satisfies_all_constraints/1
中描述的内容
因此，Prolog 被称为声明性语言：您描述您希望它找到什么。您并不特别关心如何它找到这些解决方案。
请注意，通过使用 setof/3，您可以绕过这种隐式回溯，并将所有解决方案具体化为一个 Prolog 项，您可以在 中 您的程序中进行推理。这可能很有用，例如，如果您想以不同的顺序探索分支，或者在 Prolog 中完全实施其他搜索策略。对于天真的方法，不需要 setof/3，而是需要对您想要找到的解决方案的清晰描述。
较长的答案是，这种方法（也称为 "generate and test"）在某些情况下绝对非常有吸引力、有用和有指导意义，例如：
- 您完全不知道无论如何如何找到您的结果
- 你想在任何情况下生成所有解决方案
- 生成所有可能性在任何情况下都不会花费很多时间
- 等等
然而，通常有非常快的方法来寻找特定的解决方案，而你的问题——虽然我不知道你到底想找到什么——似乎属于这一类.
不过，由于这也是您所要求的，我建议您至少尝试一下天真的方法（生成和测试），因为它通常会导致非常短且清楚地说明你真正想要什么，如果运气好的话，也足以得到它，至少在小的情况下是这样。
除了我在其他答案中写的内容之外，我现在想向您展示一个具体解决方案来完成您的任务。最多只需很小的修改，它就可以在 SICStus Prolog、YAP、GNU 和 SWI 中运行：
graph_enumeration(Nodes, Arcs, NPs-APs, Vs) :-
length(Nodes, N),
pairs_keys_values(NPs, Nodes, VNs),
pairs_keys_values(APs, Arcs, VAs),
all_distinct(VNs),
all_distinct(VAs),
VNs ins 1..N,
N1 #= N - 1,
VAs ins 1..N1,
append(VNs, VAs, Vs),
maplist(arc_connects(NPs), APs).
arc_connects(NPs, arc(N1,N2)-V) :-
member(N1-NV1, NPs),
member(N2-NV2, NPs),
V #= abs(NV1 - NV2).
注意关键思想：
- 我们描述解决方案的样子，即持有关于解决方案的内容
- 我们使用 CLP(FD) 约束以声明方式描述需求
- 我们通过保持在 Prolog 的纯单调子集中使解决方案非常通用。没有不纯的
!/0，没有 if-then-else，没有废话！只需描述持有什么，让 Prolog 完成剩下的工作以找到实际的解决方案。
您的初始测试用例的查询和答案示例：
?- graph_enumeration([a,b,c], [arc(a,b),arc(b,c)], E, Vs).
E = [a-_G6158, b-_G6164, c-_G6170]-[arc(a, b)-_G6176, arc(b, c)-_G6185],
Vs = [_G6158, _G6164, _G6170, _G6176, _G6185],
_G6158 in 1..3,
_G6232+_G6164#=_G6158,
all_distinct([_G6158, _G6164, _G6170]),
_G6164 in 1..3,
_G6273+_G6170#=_G6164,
_G6170 in 1..3,
_G6273 in -2.. -1\/1..2,
_G6185#=abs(_G6273),
_G6185 in 1..2,
all_distinct([_G6176, _G6185]),
_G6176 in 1..2,
_G6176#=abs(_G6232),
_G6232 in -2.. -1\/1..2 ;
false.
剩余目标意味着这是一个条件答案。有解当残差约束可以满足
为了找到具体的解决方案，我们使用枚举谓词label/1。例如：
?- graph_enumeration([a,b,c], [arc(a,b),arc(b,c)], E, Vs), label(Vs).
E = [a-1, b-3, c-2]-[arc(a, b)-2, arc(b, c)-1],
Vs = [1, 3, 2, 2, 1] ;
E = [a-2, b-1, c-3]-[arc(a, b)-1, arc(b, c)-2],
Vs = [2, 1, 3, 1, 2] ;
E = [a-2, b-3, c-1]-[arc(a, b)-1, arc(b, c)-2],
Vs = [2, 3, 1, 1, 2] ;
E = [a-3, b-1, c-2]-[arc(a, b)-2, arc(b, c)-1],
Vs = [3, 1, 2, 2, 1] ;
false.
这为您提供了在这种情况下存在的所有解决方案。再次注意 Prolog 自动 为我们生成回溯的所有解决方案。另请注意，我们可以在所有方向上使用谓词。例如，我们可以验证个解决方案，并完成部分实例化的解决方案。
所以，这是我一段时间以来一直试图解决的练习。我得到一个像这样的输入列表 [a-b,b-c]，它们是节点和连接节点的弧。条件是：
节点需要关联一个唯一编号，从1到N，
并且弧线需要关联一个唯一的数字，从 1 到 N-1，并且该数字必须是减去弧线连接的节点的结果。
所以答案是：
EnumNodos = [enum(3,a), enum(1,b), enum(2,c)],
EnumArcos = [enum(2,a‐b), enum(1,b‐c)]
因此，由于我无法为此提出算法，我也不知道是否有算法，我想，我可以尝试每一种可能性，因为我知道如果输入是正确的，这样我迟早会得到它。
我找到了一个 prolog 排列的例子，如果我给它一些输入列表，它会给出它的排列。然后（在控制台中），如果我点击';'它给了我另一个，依此类推。我正在尝试自己包含该代码。
我还没有完成，但我会提供一些帮助，特别是我尝试排列选项的 "looping" 方法。我真的不知道你会怎么说，在序言中，如果这个动作失败了，尝试另一个新的排列，不同于之前尝试过的每个排列（没有给出';'作为解决方案的输入。因为有很多排列正在进行失败，我想检查它是否失败，如果失败，请尝试另一个。
EDIT 所以我刚刚发现了 setof... 我一直在尝试，但我认为我仍然缺少一个关键部分。截至目前，我觉得我可以获得我需要的所有可能性的列表：setof(Out,perm(ListaEnum, SalidaPerm),X),
但我仍然无法接受失败然后重试的想法。到目前为止我的想法是：我得到 X 结果，然后像处理任何列表一样移动它。我检查它是否有唯一编号等等，如果没有，我想继续沿着那个 X 行驶。所以我将致力于失败而不是成功？？我应该这样做吗？？
% enumerate(CONNECTIONS_IN, NODES_OUT, ARCS_OUT)
%TODO query example of call: enumerate([a-b,b-c], EnumNodos, EnumArcos).
enumerate(C, EnumNodos, EnumArcos) :-
enum_nodes(C, [], NodeListUnique, [], PermNodes, 1),
loopPerm(C, NodeListUnique, EnumArcos, PermNodes, SalidaPerm).
% enum_nodes(CONNECTIONS_IN, NODES_IN, NODES_OUT, IDS_IN, IDS_OUT, START_ID)
% Fills up NODES_OUT with unique nodes, and PERMOUT with IDS. New IDs start at START_ID...
enum_nodes([], N, N, M, M, _).
enum_nodes([A-B | T], N, NOUT, M, PERMOUT, ID) :-
ensure_node(A, N, NTMP1, M, PERMNODESOUTA, ID, ID1),
ensure_node(B, NTMP1, NTMP2, PERMNODESOUTA, PERMNODESOUTB, ID1, ID2),
enum_nodes(T, NTMP2, NOUT, PERMNODESOUTB, PERMOUT, ID2).
% ensure_node(NODE, NODES_IN, NODES_OUT,IDS_IN, IDS_OUT, ID_IN, ID_OUT)
% Adds enum(ID_IN, NODE) to NODES_IN to produce NODES_OUT if NODE does not already exist in NODES_IN
ensure_node(NODE, NODES_IN, NODES_IN, PermNodesNOVALENin, PermNodesNOVALENin, ID, ID) :-
member(NODE, NODES_IN), !.
ensure_node(NODE, NODES_IN, [NODE | NODES_IN], PERMIN, [ID_IN|PERMIN], ID_IN, ID_OUT) :-
ID_OUT is ID_IN + 1.
%At this point I have a list of unique nodes and a list of IDs for said nodes, and I want to start calculatin permutations of this two lists until I find one that works.
loopPerm(C, NodeListUnique, EnumArcos, PermNodes, SalidaPerm):-
crearEnum(NodeListUnique, PermNodes, ListaEnum),
perm(ListaEnum, SalidaPerm),
create_arcs(C, SalidaPerm, []),
%%here is where code stops working properly
loopPerm(C, EnumNodos, EnumArcos, PermNodes, SalidaPerm).
%crear_enum(NODES_IN, IDS_IN, enumLISTout)
%creates a list of enums to be permuted, TODO the idea here is that each call will change the list, so if it failed before, it should try a new one.
crearEnum([], [], []).
crearEnum([H1 | NodeListUnique], [H2| PermNodes], [enum(H2,H1)|Salida]):-
crearEnum(NodeListUnique, PermNodes, Salida).
% create_arcs(CONNECTIONS_IN, NODES_IN, ARCS_OUT).
% Create arcs - makes a list of arc(NODE_ID_1, NODE_ID_2)...
create_arcs([], _, _).
create_arcs([A-B | T], NODES, LISTARCS) :-
ensure_arcs(A,B,NODES, LISTARCS, LISTARCS2),
create_arcs(T, NODES, LISTARCS2).
%ensure_arcs(NODE_A, NODE_B, NODELIST, LISTARCSIN, LISTARCSOUT)
%builds a list of arcs TODO works WRONG when arc already was in the input. It should fail, but it just checks that is a member and moves on. So basically it works when arcs are new, because they are added properly, but not when arcs were already found (and as per the exercise it should fail and try another permutation).
ensure_arcs(A,B,NODES, LISTARCSIN, LISTARCSIN):-
member(enum(NODE_ID_A, A), NODES),
member(enum(NODE_ID_B, B), NODES),
REMAINDER is abs(NODE_ID_A-NODE_ID_B),
member(enum(REMAINDER,_), LISTARCSIN), !.
ensure_arcs(A,B,NODES, LISTARCSIN,[enum(REMAINDER, A-B) | LISTARCSIN]):-
member(enum(NODE_ID_A, A), NODES),
member(enum(NODE_ID_B, B), NODES),
REMAINDER is abs(NODE_ID_A-NODE_ID_B).
perm([H|T], Perm) :-
perm(T, SP),
insert(H, SP, Perm).
perm([], []).
insert(X, T, [X|T]).
insert(X, [H|T], [H|NT]) :-
insert(X, T, NT).
以下是我手工制作的其他一些示例，以备不时之需。我也想道歉，因为我对代码一点也不满意，只是我需要继续前进而不是修复我确定是痛苦的错误（但我真的无法修复，截至现在，我花了太长时间才能获得任何有效的代码，即使勉强也是如此）。
6a
5 4
1b 2e
2 3
3c 5f
1
4d
EnumNodos = [enum(6,a), enum(1,b), enum(2,e), enum(3,c), enum(5,f), enum(4,d)],
EnumArcos = [enum(5,a‐b), enum(4,a-e), enum(3,e-f), , enum(2,b-c), enum(1,c-d)]
5a
4 3
1b 2e
1 2
3c 4f
EnumNodos = [enum(5,a), enum(1,b), enum(2,e), enum(3,c), enum(4,f)],
EnumArcos = [enum(4,a‐b), enum(3,a-e), enum(1,b-c), , enum(2,e-f)]
5a
4 3
1b 2e
2
3c
1
4d
简短的回答是你想做的正是 Prolog 自动所做的：它被称为回溯并且意味着 Prolog会尝试每一种可能性，直到他们都筋疲力尽。
因此，对于您的情况，您可以在概念上将整个任务表述为：
solution(S) :-
candidate(S),
satisfies_all_constraints(S).
就是这样。 Prolog 将生成所有候选解决方案并准确报告那些 "satisfy all constraints"，这是您需要在 satisfies_all_constraints/1
因此，Prolog 被称为声明性语言：您描述您希望它找到什么。您并不特别关心如何它找到这些解决方案。
请注意，通过使用 setof/3，您可以绕过这种隐式回溯，并将所有解决方案具体化为一个 Prolog 项，您可以在 中 您的程序中进行推理。这可能很有用，例如，如果您想以不同的顺序探索分支，或者在 Prolog 中完全实施其他搜索策略。对于天真的方法，不需要 setof/3，而是需要对您想要找到的解决方案的清晰描述。
较长的答案是，这种方法（也称为 "generate and test"）在某些情况下绝对非常有吸引力、有用和有指导意义，例如：
- 您完全不知道无论如何如何找到您的结果
- 你想在任何情况下生成所有解决方案
- 生成所有可能性在任何情况下都不会花费很多时间
- 等等
然而，通常有非常快的方法来寻找特定的解决方案，而你的问题——虽然我不知道你到底想找到什么——似乎属于这一类.
不过，由于这也是您所要求的，我建议您至少尝试一下天真的方法（生成和测试），因为它通常会导致非常短且清楚地说明你真正想要什么，如果运气好的话，也足以得到它，至少在小的情况下是这样。
除了我在其他答案中写的内容之外，我现在想向您展示一个具体解决方案来完成您的任务。最多只需很小的修改，它就可以在 SICStus Prolog、YAP、GNU 和 SWI 中运行：
graph_enumeration(Nodes, Arcs, NPs-APs, Vs) :-
length(Nodes, N),
pairs_keys_values(NPs, Nodes, VNs),
pairs_keys_values(APs, Arcs, VAs),
all_distinct(VNs),
all_distinct(VAs),
VNs ins 1..N,
N1 #= N - 1,
VAs ins 1..N1,
append(VNs, VAs, Vs),
maplist(arc_connects(NPs), APs).
arc_connects(NPs, arc(N1,N2)-V) :-
member(N1-NV1, NPs),
member(N2-NV2, NPs),
V #= abs(NV1 - NV2).
注意关键思想：
- 我们描述解决方案的样子，即持有关于解决方案的内容
- 我们使用 CLP(FD) 约束以声明方式描述需求
- 我们通过保持在 Prolog 的纯单调子集中使解决方案非常通用。没有不纯的
!/0，没有 if-then-else，没有废话！只需描述持有什么，让 Prolog 完成剩下的工作以找到实际的解决方案。
您的初始测试用例的查询和答案示例：
?- graph_enumeration([a,b,c], [arc(a,b),arc(b,c)], E, Vs). E = [a-_G6158, b-_G6164, c-_G6170]-[arc(a, b)-_G6176, arc(b, c)-_G6185], Vs = [_G6158, _G6164, _G6170, _G6176, _G6185], _G6158 in 1..3, _G6232+_G6164#=_G6158, all_distinct([_G6158, _G6164, _G6170]), _G6164 in 1..3, _G6273+_G6170#=_G6164, _G6170 in 1..3, _G6273 in -2.. -1\/1..2, _G6185#=abs(_G6273), _G6185 in 1..2, all_distinct([_G6176, _G6185]), _G6176 in 1..2, _G6176#=abs(_G6232), _G6232 in -2.. -1\/1..2 ; false.
剩余目标意味着这是一个条件答案。有解当残差约束可以满足
为了找到具体的解决方案，我们使用枚举谓词label/1。例如：
?- graph_enumeration([a,b,c], [arc(a,b),arc(b,c)], E, Vs), label(Vs). E = [a-1, b-3, c-2]-[arc(a, b)-2, arc(b, c)-1], Vs = [1, 3, 2, 2, 1] ; E = [a-2, b-1, c-3]-[arc(a, b)-1, arc(b, c)-2], Vs = [2, 1, 3, 1, 2] ; E = [a-2, b-3, c-1]-[arc(a, b)-1, arc(b, c)-2], Vs = [2, 3, 1, 1, 2] ; E = [a-3, b-1, c-2]-[arc(a, b)-2, arc(b, c)-1], Vs = [3, 1, 2, 2, 1] ; false.
这为您提供了在这种情况下存在的所有解决方案。再次注意 Prolog 自动 为我们生成回溯的所有解决方案。另请注意，我们可以在所有方向上使用谓词。例如，我们可以验证个解决方案，并完成部分实例化的解决方案。