Variable List Item Combinations - Prolog

Question

How can I generate all possible combinations of list items?

For example, given the list [1,2,3] , I want to develop a predicate using comb([1,2,3], L). forms comb([1,2,3], L). which should return the following answer for L :

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

Answer 1

What you request includes both combinations (selection of a subset) and permutations (reordering of the order) of the list.

The result of your example means that an empty list is not considered a valid solution, so we will exclude it in the next implementation. Reconsider if it was oversight. In addition, this implementation creates solutions in a different order than your conclusion.

 comb(InList,Out) :- splitSet(InList,_,SubList), SubList = [_|_], /* disallow empty list */ permute(SubList,Out). splitSet([ ],[ ],[ ]). splitSet([H|T],[H|L],R) :- splitSet(T,L,R). splitSet([H|T],L,[H|R]) :- splitSet(T,L,R). permute([ ],[ ]) :- !. permute(L,[X|R]) :- omit(X,L,M), permute(M,R). omit(H,[H|T],T). omit(X,[H|L],[H|R]) :- omit(X,L,R). 

Tested by Amzy! Prologue:

 ?- comb([1,2,3],L). L = [3] ; L = [2] ; L = [2, 3] ; L = [3, 2] ; L = [1] ; L = [1, 3] ; L = [3, 1] ; L = [1, 2] ; L = [2, 1] ; L = [1, 2, 3] ; L = [1, 3, 2] ; L = [2, 1, 3] ; L = [2, 3, 1] ; L = [3, 1, 2] ; L = [3, 2, 1] ; no 

Answer 2

Stay clean by defining comb/2 based on same_length/2 , prefix/2 , foldl/4 and select/3 :

 comb (As, Bs): -
    same_length (As, Full),
    Bs = [_ | _],
    prefix (Bs, Full),
    foldl (select, Bs, As, _).

Here is an example of the query specified by OP:

 ?- comb([1,2,3],Xs). Xs = [1] ; Xs = [2] ; Xs = [3] ; Xs = [1,2] ; Xs = [1,3] ; Xs = [2,1] ; Xs = [2,3] ; Xs = [3,1] ; Xs = [3,2] ; Xs = [1,2,3] ; Xs = [1,3,2] ; Xs = [2,1,3] ; Xs = [2,3,1] ; Xs = [3,1,2] ; Xs = [3,2,1] ; false. 

Ok! But what if the list specified as the first argument contains duplicates?

 ?- comb([1,1,2],Xs). Xs = [1] ; Xs = [1] % (redundant) ; Xs = [2] ; Xs = [1,1] ; Xs = [1,2] ; Xs = [1,1] % (redundant) ; Xs = [1,2] % (redundant) ; Xs = [2,1] ; Xs = [2,1] % (redundant) ; Xs = [1,1,2] ; Xs = [1,2,1] ; Xs = [1,1,2] % (redundant) ; Xs = [1,2,1] % (redundant) ; Xs = [2,1,1] ; Xs = [2,1,1] % (redundant) ; false. 

Not really! Can we get rid of redundant answers? Yes, just use selectd/3 !

 comb (As, Bs): -
    same_length (As, Full),
    Bs = [_ | _],
    prefix (Bs, Full),
    foldl (selectd, Bs, As, _).

So, re-run the query again with an improved comb/2 implementation!

 ?- comb([1,1,2],Xs). Xs = [1] ; Xs = [2] ; Xs = [1,1] ; Xs = [1,2] ; Xs = [2,1] ; Xs = [1,1,2] ; Xs = [1,2,1] ; Xs = [2,1,1] ; false. 

Answer 3

there is a predefined predicate called permutation ...

 1 ?- permutation([1,2,3],L). L = [1, 2, 3] ; L = [2, 1, 3] ; L = [2, 3, 1] ; L = [1, 3, 2] ; L = [3, 1, 2] ; L = [3, 2, 1] . 2 ?- listing(permutation). lists:permutation([], [], []). lists:permutation([C|A], D, [_|B]) :- permutation(A, E, B), select(C, D, E). lists:permutation(A, B) :- permutation(A, B, B). true. 

hope this helps.

Answer 4

Hint: this is easy to do if you wrote the inselt(X,Y,Z) predicate, which is executed if any insertion of Y into X gives Z :

 inselt([E|X], Y, [E|Z]) :- inselt(X,Y,Z). inselt(X, Y, [Y|X]). 

Then comb/3 can be recursively encoded using inselt/3 .