Get all sets of list in prolog

问题:

How can I generate all the possible sets of the elements of a list with current length?

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

UPD: there is good answer given by Sharky. But maybe it's not the best. Here is another:

get_set(X,L) :- get_set(X,L,L).

get_set([],[],_).
get_set([X|Xs],[_|T],L) :- member(X,L), get_set(Xs,T,L).

回答1:

Consider:

get_set(L0, L) :-
    length(L, Len),
    length(L0, Len),
    apply_elem(L0, L).

apply_elem([], _).
apply_elem([X|Xs], L) :-
    member(X, L),
    apply_elem(Xs, L).

Explanation:

Determining the length of the input list L as Len allows us to generate a list of unique variables, L0, via length/2. Then, we simply apply elements of L to all members of L0 via member/2, which leaves choicepoints for options, should they exist (i.e., if the list L is of length > 1). Prolog will backtrack to generate all possible combinations of elements of L into the list L0, as required.

回答2:

Based on library predicate same_length/2, we can make it work safely in "both" directions!

Simply define get_set/2 like this, using meta-predicate maplist/2:

get_set(Xs,Ys) :-
   same_length(Xs,Ys),
   maplist(list_member(Ys),Xs).

list_member(Xs,X) :- 
   member(X,Xs).

First, the sample query suggested by the OP:

?- get_set(Xs,[1,2,3]).
Xs = [1,1,1] ;
Xs = [1,1,2] ;
Xs = [1,1,3] ;
Xs = [1,2,1] ;
Xs = [1,2,2] ;
Xs = [1,2,3] ;
Xs = [1,3,1] ;
Xs = [1,3,2] ;
Xs = [1,3,3] ;
Xs = [2,1,1] ;
Xs = [2,1,2] ;
Xs = [2,1,3] ;
Xs = [2,2,1] ;
Xs = [2,2,2] ;
Xs = [2,2,3] ;
Xs = [2,3,1] ;
Xs = [2,3,2] ;
Xs = [2,3,3] ;
Xs = [3,1,1] ;
Xs = [3,1,2] ;
Xs = [3,1,3] ;
Xs = [3,2,1] ;
Xs = [3,2,2] ;
Xs = [3,2,3] ;
Xs = [3,3,1] ;
Xs = [3,3,2] ;
Xs = [3,3,3] ;
false.                      % terminates universally

Let's try the other way round!

?- get_set([1,2,3],Ys).
Ys = [1,2,3] ;
Ys = [1,3,2] ;
Ys = [2,1,3] ;
Ys = [3,1,2] ;
Ys = [2,3,1] ;
Ys = [3,2,1] ;
false.                      % terminates universally