Permuted combinations of the elements of a list - Prolog

Question

How can I generate all the possible combinations of the elements of a list?

For example, given the list [1,2,3], I want to design a predicate with the form 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]

[1] isn't usually called a combination of [1,2,3]: I'm guessing this isn't what you mean. — Charles Stewart, Jan 02 '11 at 14:35

score 12 · Accepted Answer · answered Jan 02 '11 at 15:11

12

What you are asking for involves both combinations (selecting a subset) and permutations (rearranging the order) of a list.

Your example output implies that the empty list is not considered a valid solution, so we will exclude it in the implementation that follows. Reconsider if this was an oversight. Also this implementation produces the solutions in a different order than your example output.

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 with Amzi! Prolog:

?- 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

answered Jan 02 '11 at 15:11

hardmath

8,753
2
37
65

1

What is this `!` for? – false Jul 24 '15 at 17:02
@false: I think there is only one cut, in the first clause for `permute/2`, and this is for efficiency (aka "green cut"). – hardmath Jul 24 '15 at 17:07
3

Red usage: `permute(Xs, Ys), Xs = [_]` – false Jul 24 '15 at 18:43
1

@false: I think your observation is more about my predicate `permute/2` not supporting uninstantiated first arguments. The Question concerns how to produce "all the possible combinations of the elements of a list" ... "given the list", so my implementation was aimed at efficiency for that mode. See the [SWI-Prolog notation description](http://www.swi-prolog.org/pldoc/man?section=preddesc) for mode indicators. – hardmath Jul 24 '15 at 19:57
3

You are right, but still your answer contains this problematic code. – false Jul 24 '15 at 20:12
@false: I think I would get a better understanding of your point of view in chat. – hardmath Jul 24 '15 at 20:15
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/84220/discussion-between-false-and-hardmath). – false Jul 24 '15 at 20:16

score 5 · Answer 2 · edited May 23 '17 at 12:16

5

Stay pure 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's the sample query given by the 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 given 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 quite! Can we get rid of above redundant answers? Yes, simply use selectd/3!

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

So let's re-run above query again with the improved implementation of comb/2!

?- 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.

edited May 23 '17 at 12:16

Community

1
1

answered Jul 28 '15 at 09:17

repeat

18,496
4
54
166

4

Great solution, +1! I hope we will soon see a library containing all these pure elementary predicates! `library(purple)`: *Pure Prolog Library (Elementary)*? – mat Jul 28 '15 at 11:26
Note: This also needs `:- use_module(library(lists)).` and [if_/3](https://stackoverflow.com/a/27358600/1243762) – Guy Coder Jan 25 '19 at 15:03
@GuyCoder. You're right. The dependency on `if_/3` is not immediately visible, but I'm linking to the definition of `selectd/3`... good enough? – repeat Jan 25 '19 at 15:56
@GuyCoder. What would you suggest? The asker might want to get self-contained answers to reproduce experiments (shown in an answer) easily. But how to do that (with different Prolog systems, libraries, etc.)? – repeat Jan 25 '19 at 16:23
The reason I looked at this answer is because I am generating data for test cases and while combinations and permutations work fine when I have 3 or more items in the set, when there is only 2 items in the set and I need to generate a pattern with 3 items, how do I extend the set. This [answer](https://stackoverflow.com/q/42233085/1243762) appears to have what I seek, Just need to check it now. – Guy Coder Jan 25 '19 at 16:31

score 2 · Answer 3 · answered Jan 03 '11 at 05:57

2

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 ..

answered Jan 03 '11 at 05:57

AhmadAssaf

3,556
5
31
42

1

It's definitely helpful for seeing how one can go about describing permutations (+1!). An instructive feature of this code is that `permutation/3` is *not* tail recursive, and that exchanging the two goals typically increases runtime by a large margin. It's also elegant and nice to look at, involving only pure code. Note though that OP asks for something slightly different: The question is about permutations of subsequences, not necessarily comprising the whole list. Check out @repeat's short, elegant and pure solution! – mat Jul 28 '15 at 11:21

score 0 · Answer 4 · edited Jul 28 '15 at 08:42

0

Hint: This is easy to do if you have written a predicate inselt(X,Y,Z), which holds 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 coded recursively using inselt/3.

edited Jul 28 '15 at 08:42

repeat

18,496
4
54
166

answered Jan 02 '11 at 14:36

Charles Stewart

11,661
4
46
85

Permuted combinations of the elements of a list - Prolog

4 Answers4

Linked