Kết hợp được phép của các thành phần trong danh sách - Prolog

Question

Làm cách nào để tôi có thể tạo tất cả các kết hợp có thể có của các thành phần trong danh sách?

Ví dụ, đưa ra danh sách [1,2,3], tôi muốn thiết kế một vị với hình thức comb([1,2,3], L). mà nên trả lại câu trả lời sau đây cho 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]

Answer 1

Những gì bạn đang yêu cầu bao gồm cả kết hợp (chọn tập con) và hoán vị (sắp xếp lại thứ tự) của danh sách.

Kết quả ví dụ của bạn ngụ ý rằng danh sách trống không được coi là giải pháp hợp lệ, vì vậy chúng tôi sẽ loại trừ nó trong quá trình triển khai sau. Xem xét lại nếu đây là một sự giám sát. Việc triển khai này cũng tạo ra các giải pháp theo thứ tự khác với kết quả ví dụ của bạn.

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

Đã thử nghiệm với 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 

Answer 2

Gợi ý: Đây là dễ dàng để làm gì nếu bạn đã viết một vị inselt(X,Y,Z), nắm giữ nếu có chèn của Y thành X cho Z:

inselt([E|X], Y, [E|Z]) :- inselt(X,Y,Z). 
inselt(X, Y, [Y|X]). 

Sau đó comb/3 có thể được mã hóa một cách đệ quy sử dụng inselt/3.

Answer 3

có một vị được xác định trước gọi là hoán vị ...

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. 

hy vọng điều này giúp ..

Answer 4

Ở tinh khiết bằng cách định nghĩa comb/2 dựa trên same_length/2, prefix/2, foldl/4 và select/3 :

 
comb(As,Bs) :- 
    same_length(As,Full), 
    Bs = [_|_], 
    prefix(Bs,Full), 
    foldl(select,Bs,As,_). 

Đây là truy vấn mẫu do OP cung cấp:

?- 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! Nhưng nếu danh sách được đưa ra như đối số đầu tiên chứa các bản sao thì sao?

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

Không hoàn toàn! Chúng tôi có thể loại bỏ các câu trả lời thừa không? Có, chỉ cần sử dụng selectd/3!

 
comb(As,Bs) :- 
    same_length(As,Full), 
    Bs = [_|_], 
    prefix(Bs,Full), 
    foldl(selectd,Bs,As,_). 

Vì vậy, hãy chạy lại truy vấn ở trên với việc triển khai được cải thiện 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.