So, this is an exercise that I've been trying to solve for some time now. I get an input list like this [a-b,b-c], which are nodes and arcs connecting nodes. The conditions are:
Nodes need to have an unique number associated, from 1 to N,
and arcs are required to have an unique number associated, from 1 to N-1, AND that number has to be the result of substracting the nodes that arc connects.
So the answer would be:
EnumNodos = [enum(3,a), enum(1,b), enum(2,c)],
EnumArcos = [enum(2,a‐b), enum(1,b‐c)]
So since I haven't been able to come up with an algorith for this, nor do I know if there is one, I thought, I could try every single possibility, since I know there IS a solution if the input is correct, and that way sooner or later I will get it.
I found an example of prolog permutation in which, if I give it some input list, it gives a permutation of it. Then (in console), if I hit ';' it gives me another one, and so on. I'm trying to include that code on my own.
I haven't finished yet but I would some help, specifically with the "looping" method in which I try to permute the options. I do not really know how you would say, in prolog, if this actions failed, try another, new permutation, different from each permutation tried before (WITHOUT giving ';' as input for the solution. Since there are many permutations that are going to fail, I want to check whether or not it fails, and if it does, try another one.
EDIT so I just found out setof... and I've been trying it out and I think I'm still missing one key part. As of right now I feel like I can get a list of every possibility I need with this: setof(Out,perm(ListaEnum, SalidaPerm),X),
But I still have trouble with the idea of FAILING then retrying. My idea so far is: I get the X result, and travel it as I would with any list. I check whether or not it does have unique numbers and so on, and if it does not, I want to keep traveling that X. So I would be working on failure instead of success?? Should I even be doing this??
% 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).
Here are some other examples I worked by hand in case they are needed. I also wanted to apologize because I'm not happy with the code in the slightest, it's just that I need to keep going instead of fixing what I'm sure are painful mistakes (but that I am not really able to fix, as of right now, it takes me way too long to get any code that works, even if barely).
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
The short answer is that what you want to do is exactly what Prolog does automatically: It is called backtracking and means that Prolog will try every possibility until they are all exhausted.
So, in your case, you can formulate your whole task conceptually as:
solution(S) :-
candidate(S),
satisfies_all_constraints(S).
That's it. Prolog will generate all candidate solutions and report exactly those that "satisfy all constraints", which is what you need to describe in satisfies_all_constraints/1
For this reason, Prolog is called a declarative language: You describe what you want it to find. You do not particularly care how it finds these solutions.
Note that by using setof/3 you circumvent this implicit backtracking and reify all solutions into a Prolog term that you can reason about within your program. This may be useful for example if you want to explore branches in a different order, or implement other search strategies altogether within Prolog. For the naive approach, no setof/3 is needed, but rather a clear description of the solutions you want to find.
The longer answer is that such an approach (also called "generate and test") is definitely very appealing, useful and instructive in several cases, such as:
However, there are often vastly faster approaches for finding particular solutions, and your problem—although I have no idea what you actually want to find—seems to fall into this category.
Still, since this is also what you are asking for, I recommend you at least try the naive approach (generate and test), since it often results in very short and clear specifications of what you actually want, and with some luck, suffices to also get it, at least in small instances.