Длина заказанных подмножеств?

Question

Я пытаюсь создать код, который генерирует все подмножества набора для заказа. То есть, вызов subset([1,2,3], X) должен генерировать

X = []; 
X = [1]; 
X = [2]; 
X = [3]; 
X = [1,2]; 
X = [1,3]; 
X = [2,3]; 
X = [1,2,3]. 

Внутренний порядок не все, что важно, только что наименьшие подмножества перечислены первые (т.е. я не волнует, если предшествует [1 [2,3] , 2], только 1, [2] и [3] до [2,3]).

-

Я пробовал два подхода до сих пор. Сначала я попытался сделать предикат сам ...

subset([], []). 
subset(List, []). 
subset(List, [N]) :- 
    member(N, List). 

subset(List, [N|Rest]) :- 
    !, 
    nth0(I, List, N), 
    findall(E, (nth0(J, List, E), J > I), NewList), 
    subset2(NewList, Rest). 

... но он даже не подходит для работы по назначению. Во-вторых, я попробовал сделать poweret (используя this subset predicate) и заказать с list_to_ord_set/2, но я не мог заставить его работать.

Помощь?

Answer 1

я нашел не так элегантное решение ... это требует вырезать и некоторые встроенные команды

subset(Xs, Ys) :- 
    length(Xs, L), 
    between(0, L, N), 
    length(Ys, N), 
    assign(Xs, Ys). 

assign(_, []) :- !. 
assign([X|Xs], [X|Ys]) :- 
    assign(Xs, Ys). 
assign([_|Xs], Ys) :- 
    assign(Xs, Ys). 

как отметил @Fatalize, мы можем избежать вырезать, просто заставляя пустой список по первому аргументу 1^п:

assign([], []). 
assign([X|Xs], [X|Ys]) :- 
    assign(Xs, Ys). 
assign([_|Xs], Ys) :- 
    assign(Xs, Ys). 

я избегал поменять 2^и 3^статьи, так что "естественный порядок все еще хорошо сохранились

Answer 2

Всегда также рассмотреть возможность использования DCG notation WHe n описание списков.

Например:

list_sublist(Ls0, Ls) :- 
     same_length(Ls0, Ls1), 
     append(Ls, _, Ls1), 
     phrase(sublist(Ls0), Ls). 

sublist([])  --> []. 
sublist([L|Ls]) --> ([] ; [L]), sublist(Ls). 

Пример запроса:

?- list_sublist([a,b,c], Ls). 
Ls = [] ; 
Ls = [c] ; 
Ls = [b] ; 
Ls = [a] ; 
Ls = [b, c] ; 
Ls = [a, c] ; 
Ls = [a, b] ; 
Ls = [a, b, c] ; 
false. 

Другой пример:

?- list_sublist(Ls, [b,c]). 
Ls = [b, c] ; 
Ls = [_G511, b, c] ; 
Ls = [b, _G514, c] ; 
Ls = [b, c, _G517] ; 
etc. 

Наиболее общий случай:

?- list_sublist(Xs, Ys). 
Xs = Ys, Ys = [] ; 
Xs = [_G513], 
Ys = [] ; 
Xs = Ys, Ys = [_G513] 
Xs = [_G513, _G516], 
Ys = [] ; 
etc.