Subsets trong Prolog

Question

Tôi đang tìm kiếm một vị ngữ mà làm việc như thế này:

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

Tôi đã nhìn thấy một số subset triển khai, nhưng tất cả đều làm việc khi bạn muốn kiểm tra xem một danh sách là một tập hợp con của khác, không phải khi bạn muốn tạo ra các tập con. Bất kỳ ý tưởng?

Answer 1

On http://www.probp.com/publib/listut.html bạn sẽ tìm thấy một thực hiện của một vị gọi subseq0 mà những gì bạn muốn:

subseq0(List, List). 
subseq0(List, Rest) :- 
    subseq1(List, Rest). 

subseq1([_|Tail], Rest) :- 
    subseq0(Tail, Rest). 
subseq1([Head|Tail], [Head|Rest]) :- 
    subseq1(Tail, Rest). 

Một giải thích ngắn gọn: subseq0(X, Y) kiểm tra xem Y là một tập con dãy con của X, trong khi subseq1(X, Y) kiểm tra liệu Y có phải là thích hợp tập hợp con sau đó của X.

Do đại diện mặc định của tập hợp là danh sách không có yếu tố iQue, bạn có thể sử dụng nó để có được tất cả các tập con như trong ví dụ sau:

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

Answer 2

Ở đây đi một thực hiện:

subset([], []). 
subset([E|Tail], [E|NTail]):- 
    subset(Tail, NTail). 
subset([_|Tail], NTail):- 
    subset(Tail, NTail). 

Nó sẽ tạo ra tất cả các tập con, mặc dù không theo thứ tự hiển thị trên ví dụ của bạn.

Theo yêu cầu của người nhận xét ở đây, hãy giải thích:

Điều khoản đầu tiên là trường hợp cơ sở. Nó nói rằng danh sách trống là một tập hợp con của danh sách trống.

Điều khoản thứ hai và thứ ba đối phó với đệ quy. Mệnh đề thứ hai nói rằng nếu hai danh sách có cùng một Head và đuôi của danh sách bên phải là một tập con của đuôi của danh sách bên trái, thì danh sách bên phải là một tập hợp con của danh sách bên trái.

Điều khoản thứ ba quy định rằng nếu chúng ta bỏ qua phần đầu của danh sách bên trái và danh sách bên phải là tập con của đuôi của danh sách bên trái, thì danh sách bên phải là tập con của danh sách bên trái.

Quy trình được hiển thị ở trên tạo bộ đặt hàng. Đối với bộ có thứ tự bạn có thể sử dụng permutation/3:

unordered_subset(Set, SubSet):- 
    length(Set, LSet), 
    between(0,LSet, LSubSet), 
    length(NSubSet, LSubSet), 
    permutation(SubSet, NSubSet), 
    subset(Set, NSubSet). 

Answer 3

append([],L,L). 

append([H|T],L,[H|L1]):-append(T,L,L1). 


subset([X|T],[X|L]) :-subset(T,L). 

subset([X|T],[G|L]) :-subset([X],L),append(L2,[X|L3],[G|L]),append(L2,L3,L4),subset(T,L4). 

subset([],_). 

---------------------------------------------- 
?- subset([1,2],[1,2]). 

yes 

?- subset([1,2],[2,1]). 

yes 

?- subset([1,1],[1,2]). 

no 

?- subset(D,[1,2]). 

D = [1,2] ; 

D = [1] ; 

D = [2,1] ; 

D = [2] ; 

D = '[]' ; 

no 

Answer 4

Set là một bộ sưu tập của biệt đối tượng theo định nghĩa. Một thủ tục tập hợp con không nên quan tâm về thứ tự của các phần tử trong tập hợp (trong các đối số). Một giải pháp thích hợp (SWI-Prolog) có thể trông giống như:

subset(_, []). 
subset([X|L], [A|NTail]):- 
    member(A,[X|L]),  
    subset(L, NTail), 
    not(member(A, NTail)). 

Đối với câu hỏi - tập hợp con ([1,2,3], E) nó sẽ tạo ra:

E = [] ; 
E = [1] ; 
E = [1, 2] ; 
E = [1, 2, 3] ; 
E = [1, 3] ; 
E = [2] ; 
E = [2, 3] ; 
E = [3] ; 
E = [3, 2] ; 
false. 

Hy vọng nó sẽ giúp !