Độ dài của các tập hợp con đã đặt hàng?

Question

Tôi đang cố gắng tạo mã để tạo tất cả các tập hợp con của một tập hợp theo thứ tự. Đó là, gọi subset([1,2,3], X) nên tạo

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

Trình tự nội bộ không phải là tất cả những gì quan trọng, chỉ là tập con nhỏ nhất được liệt kê đầu tiên (tức là tôi không quan tâm nếu [2,3] đến trước [1 , 2], chỉ có 1, [2] và [3] là trước [2,3]).

-

Tôi đã thử hai cách tiếp cận cho đến nay. Trước tiên, tôi đã cố gắng tự tạo vị ngữ cho mình ...

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

... nhưng nó thậm chí còn không hoạt động như dự định. Thứ hai tôi đã cố gắng làm cho các powerset (sử dụng this subset predicate) và đặt hàng với list_to_ord_set/2, nhưng tôi không thể làm cho nó hoạt động.

Trợ giúp?

Answer 1

Tôi đã tìm thấy một giải pháp không tao nhã như vậy ... nó đòi hỏi một vết cắt và một số lệnh nội trú

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

như ghi nhận của @Fatalize, chúng ta có thể tránh được việc cắt giảm, chỉ cần buộc các danh sách trống trên số đầu tiên trong tổng số 1^khoản:

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

tôi tránh để hoán đổi 2^3^khoản, do đó thứ tự 'tự nhiên' vẫn độc đáo bảo quản

Answer 2

Luôn cũng xem xét sử dụng DCG notation whe n mô tả danh sách.

Ví dụ: truy vấn

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

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

mẫu:

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

Một ví dụ khác: trường hợp

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

chung nhất:

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