Predicate gives list of unbound variables instead of all possible lists

Question

Let's say I have a list L1 = [1,2,3], I want to write a predicate that can find all permutations of this list i.e

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

Note: I know permutation(L1, L2). does exactly this, but I want to write my own predicate that does this for an exercise.

I'm a prolog rookie, so I thought lets first make a predicate that returns truewhen two lists L1 and L2 are permutations of eachother. The requirements for that are:

They need to be the same length
Every element in L1 has to be in L2

So I came up with this:

permute(L1,L2):-
    forall(member(X,L1), member(X,L2)), % every element that is a member in L1 has to be a member in L2
    length(L1,A), % the length of the list L1 is A
    length(L2,A). % AND the length of the list L2 is A

So when I query permute([1,2,3], [1,3,2]).I do get true as expected, and permute([1,2,3], [1,3]). and permute([1,2,3], [1,3,4]). both give false. So my predicate works to see if 2 lists are permutations of eachother.

But if I ask: permute([1,2,3], A). I want to be able to see all valid A, i.e all permutations of [1,2,3]. Instead I get unbounded variables. Something like A = [_942, _948, _954].

Why does this happen, why can't i look through all possible lists A? Is there a simple way to modify my code to make that happen?

The problem is that you're approaching this iwhere L is L1 with mperatively like a C program. Try defining permutation` as a relationship between the lists, and think recursively. permutation([], []). is true in the base case. Then you could have another rule that defines the permutation of a list L in terms of L1 that has an element removed L. So P is a permutation of L if I remove X from L giving L1, P1 is a permutation of L1, and then I insert X anywhere into P1 giving P. If you search this site for [prolog] permutation there should be lots of examples. — lurker

Will Ness Will Ness · Accepted Answer · 2018-10-09T18:30:31

First of all your two points definition is wrong. According to it, permute( [1,1,2], [1,2,2]) should hold (and it does).

The "simple" way is to use select/3,

select( [A|B], X):- select(A, X, Y), select(B, Y).
select( [], []).

And it works, but only in one direction. Even adding (simple) same_length doesn't help:

permute( A, B):- same_length( A, B), select( B, A).

same_length( A, B):- length(A, N), length(B, N).   % wrong

% permute( [1,2,3], X).    % OK
% permute( X, [1,2,3]).    % doesn't terminate after the last solution

No, same_length/2 must be defined carefully, as

same_length( [], []).
same_length( [_|A], [_|B]):- same_length(A, B).

Then permute is OK in both directions.

Predicate gives list of unbound variables instead of all possible lists

1 Answers