1

I wrote a predicate that takes two lists, one with the links and one using those links in a valid order. Links are written as link(a, b) where their parts can be in any order and the result should be the same. A valid order for links would be [link(a, b), link(b, c), link(c, a)]. This forms a ring of links that connect with at least one element.

% Can two links be adjacent?
adjacent(link(Elem, _), link(Elem, _)).
adjacent(link(_, Elem), link(Elem, _)).
adjacent(link(_, Elem), link(_, Elem)).
adjacent(link(Elem, _), link(_, Elem)).

% Swap the parts in a link.
swapped(link(A, B), link(B, A)).

% Is each item unique in the list?
unique(List) :- \+ (select(Elem, List, Res), memberchk(Elem, Res)).

% Can the list form a loop using only the provided links?
ring(List, Ring) :-
    length(Ring, Length),
    Length > 2, % List is at least of length 3.
    Ring = [First|_],
    last(Ring, Last),
    adjacent(First, Last), % First and last have to be able to be adjacent.
    unique(Ring), % No repeated items.
    linked(List, Ring). % Are the middle links adjacent?

% Are any of the two elements in a list?
member_or(Elem, _, List) :- member(Elem, List).
member_or(_, Elem, List) :- member(Elem, List).

% Is the list able to be linked using only the provided links?

linked(_, []).
linked(List, [Elem]) :-
    swapped(Elem, Alt),
    member_or(Elem, Alt, List). % Is the item valid?
linked(List, [First|Ring]) :-
    swapped(First, Alt),
    member_or(First, Alt, List), % Is the first item valid?
    Ring = [Second|_],
    adjacent(First, Second), % Can the next item be adjacent?
    linked(List, Ring). % Is the same operation true with one less item?

When using it as ring([link(a, b), link(b, c), link(a, c), link(f, r)], [link(a, b), link(b, c), link(c, a)]). (putting all the arguments), it always returns the correct boolean (in this case, true). Ideally, I would want to write ring([link(a, b), link(b, c), link(c, a), link(f, r)], Ring). and all the possible Rings would be given, but this freezes the interpreter (I'm using SWI-Prolog, just in case) and never spits anything out. Is this some infinite loop or just faulty logic? (Or something else?)

false
  • 10,264
  • 13
  • 101
  • 209
Camto
  • 23
  • 1
  • 9

1 Answers1

2

Let's examine the trace:

?- trace, ring([link(a, b), link(b, c), link(c, a), link(f, r)], Ring).
   Call: (9) ring([link(a, b), link(b, c), link(c, a), link(f, r)], _452) ? creep
   Call: (10) length(_452, _828) ? creep
   Exit: (10) length([], 0) ? creep
   Call: (10) 0>2 ? creep
   Fail: (10) 0>2 ? creep
   Redo: (10) length(_452, _828) ? creep
   Exit: (10) length([_812], 1) ? creep
   Call: (10) 1>2 ? creep
   Fail: (10) 1>2 ? creep
   Redo: (10) length([_812|_814], _840) ? creep
   Exit: (10) length([_812, _824], 2) ? creep
   Call: (10) 2>2 ? creep
   Fail: (10) 2>2 ? creep

Not interesting until we get to here:

   Redo: (10) length([_812, _824|_826], _852) ? creep
   Exit: (10) length([_812, _824, _836], 3) ? creep
   Call: (10) 3>2 ? creep
   Exit: (10) 3>2 ? creep
   Call: (10) [_812, _824, _836]=[_848|_850] ? creep
   Exit: (10) [_812, _824, _836]=[_812, _824, _836] ? creep
   Call: (10) lists:last([_812, _824, _836], _870) ? creep
   Exit: (10) lists:last([_812, _824, _836], _836) ? creep
   Call: (10) adjacent(_812, _836) ? creep
   Exit: (10) adjacent(link(_854, _856), link(_854, _862)) ? creep
   Call: (10) unique([link(_854, _856), _824, link(_854, _862)]) ? creep
   Call: (11) lists:select(_880, [link(_854, _856), _824, link(_854, _862)], _884) ? creep
   Exit: (11) lists:select(link(_854, _856), [link(_854, _856), _824, link(_854, _862)], [_824, link(_854, _862)]) ? creep
   Call: (11) memberchk(link(_854, _856), [_824, link(_854, _862)]) ? creep
   Exit: (11) memberchk(link(_854, _856), [link(_854, _856), link(_854, _862)]) ? creep
   Fail: (10) unique([link(_854, _856), _824, link(_854, _862)]) ? creep
   Redo: (10) adjacent(_812, _836) ? creep
   Exit: (10) adjacent(link(_854, _856), link(_856, _862)) ? creep
   Call: (10) unique([link(_854, _856), _824, link(_856, _862)]) ? creep
   Call: (11) lists:select(_880, [link(_854, _856), _824, link(_856, _862)], _884) ? creep
   Exit: (11) lists:select(link(_854, _856), [link(_854, _856), _824, link(_856, _862)], [_824, link(_856, _862)]) ? creep
   Call: (11) memberchk(link(_854, _856), [_824, link(_856, _862)]) ? creep
   Exit: (11) memberchk(link(_854, _856), [link(_854, _856), link(_856, _862)]) ? creep
   Fail: (10) unique([link(_854, _856), _824, link(_856, _862)]) ? creep
   Redo: (10) adjacent(_812, _836) ? creep
   Exit: (10) adjacent(link(_854, _856), link(_860, _856)) ? creep
   Call: (10) unique([link(_854, _856), _824, link(_860, _856)]) ? creep
   Call: (11) lists:select(_880, [link(_854, _856), _824, link(_860, _856)], _884) ? creep
   Exit: (11) lists:select(link(_854, _856), [link(_854, _856), _824, link(_860, _856)], [_824, link(_860, _856)]) ? creep
   Call: (11) memberchk(link(_854, _856), [_824, link(_860, _856)]) ? creep
   Exit: (11) memberchk(link(_854, _856), [link(_854, _856), link(_860, _856)]) ? creep
   Fail: (10) unique([link(_854, _856), _824, link(_860, _856)]) ? creep
   Redo: (10) adjacent(_812, _836) ? creep
   Exit: (10) adjacent(link(_854, _856), link(_860, _854)) ? creep
   Call: (10) unique([link(_854, _856), _824, link(_860, _854)]) ? creep
   Call: (11) lists:select(_880, [link(_854, _856), _824, link(_860, _854)], _884) ? creep
   Exit: (11) lists:select(link(_854, _856), [link(_854, _856), _824, link(_860, _854)], [_824, link(_860, _854)]) ? creep
   Call: (11) memberchk(link(_854, _856), [_824, link(_860, _854)]) ? creep
   Exit: (11) memberchk(link(_854, _856), [link(_854, _856), link(_860, _854)]) ? creep
   Fail: (10) unique([link(_854, _856), _824, link(_860, _854)]) ? creep
   Redo: (10) length([_812, _824, _836|_838], _864) ? creep
   Exit: (10) length([_812, _824, _836, _848], 4) ? creep
   Call: (10) 4>2 ? creep
   Exit: (10) 4>2 ? creep
   Call: (10) [_812, _824, _836, _848]=[_860|_862] ? creep
   Exit: (10) [_812, _824, _836, _848]=[_812, _824, _836, _848] ?

There are two salient facts here that are worth noticing:

  1. You do indeed move on to length-4 lists, so you do have some kind of logic error here.
  2. I feel like you are generating the same possibilities several times, so you're working pretty hard to not generate answers. At a first glance, it looks like adjacent/2 is helping you produce four versions of the same arrangement of variables to check. This seems inefficient.

What's missing from the trace? linked/2. Why? Because we never successfully unified unique/1! Indeed, this fails pretty much always:

?- unique([A,B]).
false.

?- unique([A,B,C]).
false.

?- unique([A]).
true.

I'd put decent odds this is your problem right here. There are better, albeit less portable, ways to do this, using dif/2. Interestingly, someone else asked about this recently, and @false linked to this answer that shows a good implementation that actually works for cases like yours. Let's substitute that definition and see what happens:

unique([]).
unique([E|Es]) :-
   maplist(dif(E), Es),
   unique(Es).

?- ring([link(a, b), link(b, c), link(c, a), link(f, r)], Ring).
Ring = [link(a, b), link(b, c), link(a, c)] ;
Ring = [link(a, b), link(b, a), link(a, c)] ;
Ring = [link(a, b), link(c, b), link(a, c)] ;
Ring = [link(a, b), link(c, a), link(a, c)] ;
Ring = [link(a, b), link(c, a), link(a, c)] ;
Ring = [link(a, b), link(b, a), link(a, c)] ;
Ring = [link(b, c), link(c, a), link(b, a)] ;

It seems fair to say this has addressed your first issue. I see a lot of duplicate solutions, so I don't think you're totally out of the woods yet, I think you still need to reconsider your adjacent/2 predicate, or your usage of it; I got 192 solutions for the list of length 3, but only 120 unique ones, which looks more like one of those factorial/combinatorics numbers I expect to see than 192.

Daniel Lyons
  • 22,421
  • 2
  • 50
  • 77