如果以前的解决方案不满足某些条件，如何尝试新的排列

Question

所以，这是一个我已经尝试解决了一段时间的练习。我得到了一个像[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排列的例子，如果我给它一些输入列表，它就会给出它的排列。然后(在控制台中)，如果我点击"；"它给了我另一个，等等。我正在尝试自己包含那个代码。

我还没有完成，但我会提供一些帮助，特别是在"循环"方法中，我试图排列选项。我真的不知道你会怎么说，在序言中，如果这个操作失败了，尝试另一个新的排列，与之前尝试的每个排列不同(没有给出"；"作为解决方案的输入。由于有很多排列都会失败，我想检查它是否失败，如果失败了，请尝试另一种。

编辑所以我刚刚发现了。。。我一直在尝试，我想我仍然缺少一个关键部分。到目前为止，我觉得我可以用这个得到我需要的每一种可能性的列表：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

Answer 1

简单的答案是，您想要做的正是Prolog自动执行的：它被称为回溯，意味着Prolog将尝试所有的可能性，直到它们都用完为止。

因此，在您的情况下，您可以将整个任务概念化为：

解决方案(S)：-候选(S)，所有约束的满足性(S)

就是这样。Prolog将生成所有候选解决方案，并准确地报告那些"满足所有约束"的解决方案，这是您需要在satisfies_all_constraints/1中描述的

因此，Prolog被称为声明性；语言：您描述您希望它查找的内容。您并不特别关心它是如何找到这些解决方案的。

请注意，通过使用setof/3，您可以绕过这种隐含的回溯，并将所有解决方案具体化为Prolog术语，您可以在程序中推理。例如，如果您想以不同的顺序探索分支，或者在Prolog中完全实现其他搜索策略，这可能会很有用。对于天真的方法，不需要setof/3，而是需要对您想要的解决方案进行清楚的描述；发现

更长的答案是，这种方法(也称为"生成和测试")在某些情况下肯定非常有吸引力、有用和有指导性，例如：

1. 您完全不知道在任何情况下如何找到您的结果
2. 在任何情况下，您都希望生成所有解决方案
3. 生成所有可能性在任何情况下都不需要花费大量时间
4. 等等

但是，通常有更快的方法来查找特定的解决方案和您的问题—尽管我不知道你到底想找到什么—似乎属于这一类。

尽管如此，由于这也是您所要求的，我建议您至少尝试天真的方法(生成和测试)，因为它通常会对您实际想要的内容产生非常简短和清晰的规范，如果运气好，也足以获得；至少在小的情况下是这样。

Answer 2

除了我在另一个答案中所写的内容外，我现在还想为您的任务展示一个具体的解决方案。它在SICStus Prolog、YAP、GNU和SWI:中运行，最多只需进行很小的修改

graph_enumeration(节点、弧、NP、AP、Vs)：-长度(节点，N)，pairs_keys_value(NP、节点、VN)，pairs_keys_value(AP、Arcs、VA)，all_ destinct(VNs)，all_ destinct(VA)，VNs in 1..N，N1#＝N-1，VA在1..N1中，append(VNs、VA、Vs)，映射列表(arc_connects(NP)、AP)。arc_connects(NP，arc(N1，N2)-V)：-成员(N1-NV1、NP)，成员(N2-NV2、NP)，V#=abs(NV1-NV2)

注意关键思想：

1. 我们描述了解决方案的样子，即对解决方案的看法
2. 我们使用CLP(FD)约束来声明性地描述需求
3. 我们通过保持在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]-[弧(a，b)-G6176，弧(b，c)-G6185]，Vs=[_G6158、_G6164、_G6170、_G6176、_G6185]，_G6158在1..3，_G6232+_G6164#=_G6158，all_destict([_G6158、_G6164、_G6170])，_G6164在1..3，_G6273+_G6170#＝_G6164，_G6170在1..3，_G6273英寸-2..1-1\/1.2，_G6185#=abs(_G6273)，_G6185在1..2，all_destict([_G6176、_G6185])，_G6176在1..2，_G6176#=abs(_G6232)，_G6232英寸-2...-1\/1.2；false

残差；目标意味着这是一个有条件的答案。存在一个解iff残差约束可以得到满足。

为了找到具体的解决方案，我们使用枚举谓词label/1。例如：

？-graph_enumeration([a，b，c]，[arc(a，b)，arc(b，c)]，E，Vs)，label(Vs)。E=[a-1，b-3，c-2]-[弧(a，b)-2，弧(b，c)-1]，Vs=[1,3,2,2,1]；E=[a-2，b-1，c-3]-[弧(a，b)-1，弧(b，c)-2]，Vs=[2，1，3，1，2]；E=[a-2，b-3，c-1]-[弧(a，b)-1，弧(b，c)-2]，Vs=[2，3，1，1，2]；E=[a-3，b-1，c-2]-[弧(a，b)-2，弧(b，c)-1]，Vs=[3，1，2，2，1]；false

这将为您提供本例中存在的所有解决方案。再次注意，Prolog会自动为我们生成回溯的所有解决方案。还要注意，我们可以在所有；方向。例如，我们可以验证解决方案，并完成部分实例化的解决方案。