Permutierte Kombinationen der Elemente einer Liste - Prolog

Question

Wie kann ich alle möglichen Kombinationen der Elemente einer Liste erzeugen?

Zum Beispiel die Liste gegeben [1,2,3], ich will comb([1,2,3], L). ein Prädikat entwerfen mit der Form, die die folgende Antwort für L zurückgeben sollte:
[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

Worum Sie bitten, beinhaltet sowohl Kombinationen (Auswählen einer Teilmenge) als auch Permutationen (Umordnen der Reihenfolge) einer Liste.

Ihre Beispielausgabe impliziert, dass die leere Liste nicht als gültige Lösung betrachtet wird, daher werden wir sie in der folgenden Implementierung ausschließen. Überdenken Sie, ob dies ein Versehen war. Auch diese Implementierung erzeugt die Lösungen in einer anderen Reihenfolge als Ihre Beispielausgabe.

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

Getestet mit 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

Hinweis: Dies ist einfach zu tun, wenn Sie ein Prädikat inselt(X,Y,Z) geschrieben haben, die, wenn eine Einfügung hält von Y in X gibt Z:

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

Dann comb/3 rekursiv inselt/3 mit kodiert werden kann.

Answer 3

gibt es einen vordefinierten Prädikat Permutation genannt ...

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. 

hoffe, das hilft ..

Answer 4

rein bleiben von comb/2 definieren, basierend auf same_length/2, prefix/2, foldl/4 und select/3 :

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

Hier ist die Beispielabfrage durch die OP gegeben:

?- 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! Was aber, wenn die als erstes Argument angegebene Liste Duplikate enthält?

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

Nicht ganz! Können wir obige redundante Antworten loswerden? Ja, verwenden Sie einfach selectd/3!

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

also lasst uns wieder mit der verbesserten Umsetzung der comb/2 obige Abfrage erneut ausführen!

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