Permuted combinations of the elements of a list -

问题:

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:

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

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

回答3:

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.

回答4:

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.