3 ms·

You can do this without the intermediate step of generating all permutations simply like so: order([]). order([_]). order([X,Y|L]) :- follo

You can do this without the intermediate step of generating all permutations simply like so: order([]). order([_]). order([X,Y|L]) :- follows(Y, X), order([Y|L]). ?- length(L, 9), order(L). L = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer] . This is likely more efficient as we're cutting short the generation of most permutations. Or you can use CPL(FD) as suggested by @Avshalom below, though more heavyweight this is likely more efficient still. The most efficient though is simply to use a topological sort algorithm, which will run in linear time, unlike any of these solutions (some of which are exponential). SWI Prolog has this built-in: ?- findall(X-Y, is_behind(Y, X), Edges), vertices_edges_to_ugraph([], Edges, UG), top_sort(UG, L). L = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer].

_xgw 4y ago
Ah, interesting! I figured there would be a way without having to "brute-force" the solution by using the `permutation` predicate but I wasn't able to come up with one. I wonder if there's a way of not depending on permutation generation, nor list length. Does querying with `order(L)` require `length(L, 9)` to work? As for the topological sort solution, I assume it's what Graphviz uses under the hood in mLuby's solution! If I understand correctly, we're graphing the sequence of reindeer and then extracting the order of the nodes in the graph?
- colanderman 4y ago
  No, `order/1` generates "too-short" solutions otherwise. If you redefine `order/1` to be a little smarter, like so: order([]) :- \+ follows(_, _). order([X]) :- \+ follows(_, X). order([X,Y|L]) :- follows(Y, X), order([Y|L]). Then this works without knowing the length a priori, but it's less efficient: ?- order(L), forall((is_behind(X, _); is_behind(_, X)), member(X, L)). L = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer] . Instead I'd discover the set of names (and therefore list length) using `setof/3`; this is similarly efficient to my original solution: ?- setof(X, Y^(is_behind(X, Y); is_behind(Y, X)), M), length(M, N), length(L, N), order(L). M = [blitzen, comet, cupid, dancer, dasher, donder, prancer, rudolph, vixen], N = 9, L = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer] .
tannhaeuser 4y ago
Putting OP's and your clauses together, I get the following pure ISO Prolog program and query that you can paste directly into Quantum Prolog's in-browser execution console at https://quantumprolog.sgml.io/browser-demo/browser-demo.html https://quantumprolog.sgml.io/browser-demo/browser-demo.html for execution in no time: % Vixen should be behind Rudolph, % Prancer and Dasher, is_behind(vixen, rudolph). is_behind(vixen, prancer). is_behind(vixen, dasher). % whilst Vixen should be in front % of Dancer and Comet. is_behind(dancer, vixen). is_behind(comet, vixen). % Dancer should be behind Donder, % Blitzen and Rudolph. is_behind(dancer, donder). is_behind(dancer, blitzen). is_behind(dancer, rudolph). % Comet should be behind Cupid, % Prancer and Rudolph. is_behind(comet, cupid). is_behind(comet, prancer). is_behind(comet, rudolph). % Donder should be behind Comet, % Vixen, Dasher, Prancer and % Cupid. is_behind(donder, comet). is_behind(fonder, vixen). is_behind(donder, dasher). is_behind(donder, prancer). is_behind(donder, cupid). % Cupid should be in front of % Comet, Blitzen, Vixen, Dancer % and Rudolph. is_behind(comet, cupid). is_behind(blitzen, cupid). is_behind(vixen, cupid). is_behind(dancer, cupid). is_behind(rudolph, cupid). % Prancer should be in front of % Blitzen, Donder and Cupid. is_behind(blitzen, prancer). is_behind(donder, prancer). is_behind(cupid, prancer). % Blitzen should be behind Cupid % but in front of Dancer, Vixen % and Donder. is_behind(blitzen, cupid). is_behind(dancer, blitzen). is_behind(vixen, blitzen). is_behind(donder, blitzen). % Rudolph should be behind Prancer % but in front of Dasher, Dancer % and Donder. is_behind(rudolph, prancer). is_behind(dasher, rudolph). is_behind(dancer, rudolph). is_behind(donder, rudolph). % Finally, Dasher should be behind % Prancer but in front of Blitzen, % Dancer and Vixen. is_behind(dasher, prancer). is_behind(blitzen, dasher). is_behind(dancer, dasher). is_behind(vixen, dasher). follows(Last, First) :- is_behind(Last, First). follows(Last, First) :- is_behind(Middle, First), follows(Last, Middle). order([]). order([_]). order([X,Y|L]) :- follows(Y, X), order([Y|L]). ?- order([A,B,C,D,E,F,G,H,I])
deleted 4y ago
[deleted]

_xgw 4y ago

Ah, interesting! I figured there would be a way without having to "brute-force" the solution by using the `permutation` predicate but I wasn't able to come up with one. I wonder if there's a way of not depending on permutation generation, nor list length. Does querying with `order(L)` require `length(L, 9)` to work? As for the topological sort solution, I assume it's what Graphviz uses under the hood in mLuby's solution! If I understand correctly, we're graphing the sequence of reindeer and then extracting the order of the nodes in the graph?

colanderman 4y ago
No, `order/1` generates "too-short" solutions otherwise. If you redefine `order/1` to be a little smarter, like so: order([]) :- \+ follows(_, _). order([X]) :- \+ follows(_, X). order([X,Y|L]) :- follows(Y, X), order([Y|L]). Then this works without knowing the length a priori, but it's less efficient: ?- order(L), forall((is_behind(X, _); is_behind(_, X)), member(X, L)). L = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer] . Instead I'd discover the set of names (and therefore list length) using `setof/3`; this is similarly efficient to my original solution: ?- setof(X, Y^(is_behind(X, Y); is_behind(Y, X)), M), length(M, N), length(L, N), order(L). M = [blitzen, comet, cupid, dancer, dasher, donder, prancer, rudolph, vixen], N = 9, L = [prancer, cupid, rudolph, dasher, blitzen, vixen, comet, donder, dancer] .

tannhaeuser 4y ago

Putting OP's and your clauses together, I get the following pure ISO Prolog program and query that you can paste directly into Quantum Prolog's in-browser execution console at https://quantumprolog.sgml.io/browser-demo/browser-demo.html https://quantumprolog.sgml.io/browser-demo/browser-demo.html for execution in no time: % Vixen should be behind Rudolph, % Prancer and Dasher, is_behind(vixen, rudolph). is_behind(vixen, prancer). is_behind(vixen, dasher). % whilst Vixen should be in front % of Dancer and Comet. is_behind(dancer, vixen). is_behind(comet, vixen). % Dancer should be behind Donder, % Blitzen and Rudolph. is_behind(dancer, donder). is_behind(dancer, blitzen). is_behind(dancer, rudolph). % Comet should be behind Cupid, % Prancer and Rudolph. is_behind(comet, cupid). is_behind(comet, prancer). is_behind(comet, rudolph). % Donder should be behind Comet, % Vixen, Dasher, Prancer and % Cupid. is_behind(donder, comet). is_behind(fonder, vixen). is_behind(donder, dasher). is_behind(donder, prancer). is_behind(donder, cupid). % Cupid should be in front of % Comet, Blitzen, Vixen, Dancer % and Rudolph. is_behind(comet, cupid). is_behind(blitzen, cupid). is_behind(vixen, cupid). is_behind(dancer, cupid). is_behind(rudolph, cupid). % Prancer should be in front of % Blitzen, Donder and Cupid. is_behind(blitzen, prancer). is_behind(donder, prancer). is_behind(cupid, prancer). % Blitzen should be behind Cupid % but in front of Dancer, Vixen % and Donder. is_behind(blitzen, cupid). is_behind(dancer, blitzen). is_behind(vixen, blitzen). is_behind(donder, blitzen). % Rudolph should be behind Prancer % but in front of Dasher, Dancer % and Donder. is_behind(rudolph, prancer). is_behind(dasher, rudolph). is_behind(dancer, rudolph). is_behind(donder, rudolph). % Finally, Dasher should be behind % Prancer but in front of Blitzen, % Dancer and Vixen. is_behind(dasher, prancer). is_behind(blitzen, dasher). is_behind(dancer, dasher). is_behind(vixen, dasher). follows(Last, First) :- is_behind(Last, First). follows(Last, First) :- is_behind(Middle, First), follows(Last, Middle). order([]). order([_]). order([X,Y|L]) :- follows(Y, X), order([Y|L]). ?- order([A,B,C,D,E,F,G,H,I])

deleted 4y ago

[deleted]