CODEWITHSUNDEEP
listprologshuffle
BlueRyse
BlueRyse

Reputation: 35

Why is my Prolog exercise not trying other solutions?

I'm trying a college assignment in Prolog, and I have some questions. This is the exercise text, I hope it's clear I'm translating from Italian:

Write a predicate arrange(List1, List2, K) that when given a List1 of at least two elements with only numbers between the range [0..100], is satisfied when List2 is a list obtained re-shuffling the elements of List1 in a way that the absolute difference between two consecutive elements is always greater than K.

Example:

?- arrange([1, 2, 3], L2, 0). 
L2 = [1, 2, 3];
L2 = [1, 3, 2];
L2 = [2, 1, 3];
L2 = [2, 3, 1];
L2 = [3, 1, 2];
L2 = [3, 2, 1];

I've tried to create my own solution, but it doesn't give me all the possible results, instead, I get only one of the possible result. I also have a colleague's solution that gives all the results, but it has one problem that I was trying to fix.

Here's my solution:

arrange(L1,L3,Diff):-
    arrange(L1,[],L3,Diff).
arrange(L1,L2,L3,Diff):-
    same_length(L1,L3),
    shuffle(L1,L2,L3),
    constraint(L3,Diff).

constraint([X1,X2],Diff):-
    int_0_100(X1),
    int_0_100(X2),
    diff(X1,X2,Diff).
constraint([X1,X2|Others],Diff):-
    int_0_100(X1),
    int_0_100(X2),
    diff(X1,X2,Diff),
    constraint([X2|Others],Diff).

shuffle([],L2,L2).
shuffle([X1|Others],L2,L3):-
    L4 = [X1 | L2],
    shuffle(Others,L4,L3).

diff(X1,X2,Diff):-
    X1 >= X2,
    X1 - X2 > Diff.
diff(X1,X2,Diff):-
    X1 < X2,
    X2 - X1 > Diff.    

int_0_100(N):-
    N >= 0, N =< 100.

same_length([],[]).
same_length([_|Others1],[_|Others2]):-
    same_length(Others1,Others2).

I guess that the problem is that I instantiate a L4 list that can't change in the shuffle predicate.

Now my colleague's solution:

arrange(L1,L2,Diff):-
    same_length(L1,L2),
    shuffle(L1,L2),
    constraint(L2,Diff).

constraint([X1,X2],Diff):-
    int_0_100(X1),
    int_0_100(X2),
    diff(X1,X2,Diff).
constraint([X1,X2|Others],Diff):-
    int_0_100(X1),
    int_0_100(X2),
    diff(X1,X2,Diff),
    constraint([X2|Others],Diff).

shuffle([],_).
shuffle([X1|Others],L2):-
    member(X1,L2),
    shuffle(Others,L2).

diff(X1,X2,Diff):-
    X1 >= X2,
    X1 - X2 > Diff.
diff(X1,X2,Diff):-
    X1 < X2,
    X2 - X1 > Diff.    
    
int_0_100(N):-
    N >= 0, N =< 100.
   
same_length([],[]).
same_length([_|Others1],[_|Others2]):-
    same_length(Others1,Others2).

As you can see there is one major difference:

This is the problem I was trying to fix, but it seems that if I don't specifically use member, instead of my solution, it just gives one possible answer.

Can you explain to me why that is, and a possible solution of the problem that the predicate member gives?

Thanks in advance for your time, I hope everything's clear enough: English is not my native language, and the problem itself is quite complicated to explain.

Upvotes: 2

Views: 96

Answers (1)

David Tonhofer
David Tonhofer

Reputation: 15338

If one looks at the "shuffles" and extracts them:

% Your shuffle:

shuffle_a(LI,LO) :-
   shuffle_help(LI,[],LO).

shuffle_help([],L2,L2).
shuffle_help([X1|Other],L2,L3):-
    shuffle_help(Other,[X1|L2],L3).


% Colleague's shuffle

shuffle_b([],_).
shuffle_b([X1|Others],L2):-
    member(X1,L2),
    shuffle_b(Others,L2).

then one sees that your shuffle just reverses the list on first argument position, whereas your colleague's "shuffle" indeed shuffles:

Note that both shuffle predicates have to be called with a list of the correct length on second argument position:

?- shuffle_a([1,2,3],[S1,S2,S3]).
S1 = 3,
S2 = 2,
S3 = 1.

?- shuffle_b([1,2,3],[S1,S2,S3]).
S1 = 1, S2 = 2, S3 = 3 ;
S1 = 1, S2 = 3, S3 = 2 ;
S1 = 2, S2 = 1, S3 = 3 ;
S1 = 3, S2 = 1, S3 = 2 ;
S1 = 2, S2 = 3, S3 = 1 ;
S1 = 3, S2 = 2, S3 = 1 ;
false.

In shuffle_a/2 there is only one way to proceed at any point.

But in shuffle_b/2, the member/2 call is able to pick one of N possible elements X1 out of the list L2 of length N. So one can tell Prolog to "redo" its choice and pick another element.

Same as

?- member(X,[1,2,3]).
X = 1 ;
X = 2 ;
X = 3.

which gives three possible answers.

Addendum

In order to correctly permute the list use permutation/2 as Guy Coder says or maybe proceed like this: A shuffle_c that uses a list of indexes 0...N-1 given to member/2 to track picking elements from the original list exactly once, and then uses nth0/3 to unify elements of the first and second list:

shuffle_c(List,OtherList) :-
   same_length(List,OtherList),
   length(List,Length),
   build_index_list(Length,IndexList),
   shuffle_by_index(IndexList,[],List,OtherList).
      
build_index_list(Length,IndexList) :-
   LengthAdj is Length-1,
   bagof(Index,between(0,LengthAdj,Index),IndexList).
    
% shuffle_by_index(IndexList,UsedIndexList,List,OtherList).

shuffle_by_index(IndexList,UsedIndexList,_,_) :- 
   same_length(IndexList,UsedIndexList).    % Success, shuffle_c will succeed with another answer
   
shuffle_by_index(IndexList,UsedIndexList,List,OtherList) :- 
   \+ same_length(IndexList,UsedIndexList), % Not done yet
   member(ToIndex,IndexList),               % Pick an "ToIndex" from IndexList
   \+member(ToIndex,UsedIndexList),         % ...that hasn't been used yet
   length(UsedIndexList,FromIndex),         % The "FromIndex" is just monotonically increasing
   format("'to index' = ~d, 'from index' = ~d. The used index list is currently: ~q~n",[ToIndex,FromIndex,UsedIndexList]),   
   nth0(FromIndex,List,X),                  % Unifies List[FromIndex] and
   nth0(ToIndex,OtherList,X),               % OtherList[ToIndex]
   shuffle_by_index(IndexList,[ToIndex|UsedIndexList],List,OtherList).

No special handling for identical elements in the original list is done.

This actually works for any of the lists uninstantiated:

?- bagof(List,
        shuffle_c(List,[1,2,3,4]),
        Bag).


Bag = [[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],
       [1,4,2,3],[1,4,3,2],[2,1,3,4],[2,1,4,3],
       [2,3,1,4],[2,3,4,1],[2,4,1,3],[2,4,3,1],
       [3,1,2,4],[3,1,4,2],[3,2,1,4],[3,2,4,1],
       [3,4,1,2],[3,4,2,1],[4,1,2,3],[4,1,3,2],
       [4,2,1,3],[4,2,3,1],[4,3,1,2],[4,3,2,1]].

And

?- bagof(List,
         shuffle_c([1,2,3,4],List),
         Bag).

Bag = [[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,4,2,3],
       [1,3,4,2],[1,4,3,2],[2,1,3,4],[2,1,4,3],
       [3,1,2,4],[4,1,2,3],[3,1,4,2],[4,1,3,2],
       [2,3,1,4],[2,4,1,3],[3,2,1,4],[4,2,1,3],
       [3,4,1,2],[4,3,1,2],[2,3,4,1],[2,4,3,1],
       [3,2,4,1],[4,2,3,1],[3,4,2,1],[4,3,2,1]].

This even works for "lists of uninstantiated elements". Feels like shuffling holes. Let's see what happens if two holes are identical

?- bagof(List,shuffle_c([A,X,X,D],List),Bag).

Bag = [[A,X,X,D],[A,X,D,X],[A,X,X,D],[A,D,X,X],
       [A,X,D,X],[A,D,X,X],[X,A,X,D],[X,A,D,X],
       [X,A,X,D],[D,A,X,X],[X,A,D,X],[D,A,X,X],
       [X,X,A,D],[X,D,A,X],[X,X,A,D],[D,X,A,X],
       [X,D,A,X],[D,X,A,X],[X,X,D,A],[X,D,X,A],
       [X,X,D,A],[D,X,X,A],[X,D,X,A],[D,X,X,A]].

This can be easily adapted to solve the original problem. We can use constraints (i.e. libray(clpfd)): We set up a constraint among subsequent elements A, B of the target list enforcing the constraint:

abs(A - B) #> K

Whenever an unification during shuffle is attempted that would violate that constraint, the unification will fail, i.e. the call nth0(ToIndex,OtherList,X) will fail for reasons that are not apparent from the code alone: because the currently live constraints veto it.

In the tracer, one sees

Call: (14) lists:nth0(1,[50,33,11,78],_40136) ? creep
Exit: (14) lists:nth0(1,[50,33,11,78],33) ? creep
Call: (14) lists:nth0(1,[50,_34818{clpfd = ...},_35522{clpfd = ...},_36226{clpfd = ...}],33) ? creep
Fail: (14) lists:nth0(1,[50,_34818{clpfd = ...},_35522{clpfd = ...},_36226{clpfd = ...}],33) ? creep

So, the new code (not bothering about the "must be between 0 and 100" constraint here) (one can probably do it even simpler as there is a ready-made 'permutation' constraint IIRC):

:- use_module(library(clpfd)).

arrange(List,OtherList,K) :-
   same_length(List,OtherList),
   apply_constraints(OtherList,K), % <----- HERE
   length(List,Length),
   build_index_list(Length,IndexList),
   shuffle_by_index(IndexList,[],List,OtherList).

% ADD THIS
      
apply_constraints([_],_).
apply_constraints([A,B|More],K) :-
   abs(A - B) #> K,
   apply_constraints([B|More],K).

% NOTHING BELOW HAS CHANGED

build_index_list(Length,IndexList) :-
   LengthAdj is Length-1,
   bagof(Index,between(0,LengthAdj,Index),IndexList).
    
% shuffle_by_index(IndexList,UsedIndexList,List,OtherList).

shuffle_by_index(IndexList,UsedIndexList,_,_) :- 
   same_length(IndexList,UsedIndexList).    % Success, shuffle_c will succeed with another answer
   
shuffle_by_index(IndexList,UsedIndexList,List,OtherList) :- 
   \+ same_length(IndexList,UsedIndexList), % Not done yet
   member(ToIndex,IndexList),               % Pick an "ToIndex" from IndexList
   \+member(ToIndex,UsedIndexList),         % ...that hasn't been used yet
   length(UsedIndexList,FromIndex),         % The "FromIndex" is just monotonically increasing
   format("'to index' = ~d, 'from index' = ~d. The used index list is currently: ~q~n",[ToIndex,FromIndex,UsedIndexList]),   
   nth0(FromIndex,List,X),                  % Unifies List[FromIndex] and
   nth0(ToIndex,OtherList,X),               % OtherList[ToIndex]
   shuffle_by_index(IndexList,[ToIndex|UsedIndexList],List,OtherList).

And so:

?- bagof(List,arrange([50,33,11,78],List,20),Bag).

Bag = [[50,11,33,78],[50,78,33,11],[50,11,78,33],
       [50,78,11,33],[11,50,78,33],[78,50,11,33],
       [33,11,50,78],[33,78,50,11],[33,11,78,50],
       [33,78,11,50],[11,33,78,50],[78,33,11,50]].

Upvotes: 2

Related Questions