Gibt es eine einfache Möglichkeit, alle Kombinationen einer Liste ohne Doppel zu erhalten. Ohne Doubles meine ich auch keine Permutationen voneinander. Also keine [a,b,c] und [c,a,b] oder [c,b,a].Alle Kombinationen einer Liste ohne Doppel in Prolog
So für die Eingabe [a, b, c] würde der Ausgang sein:
[a]
[b]
[c]
[a,b]
[a,c]
[b,c]
[a,b,c]
ich nur Lösungen mit den Doppeln (Permutationen) ist
Die Lösung für dieses Problem finden kann ziemlich einfach : es aus der leeren Menge offenbar nur eine Kombination: die leere Menge:
combs([],[]).
für jedes Element Darüber hinaus können Sie, ob Sie sie hinzufügen entscheiden oder nicht:
combs([H|T],[H|T2]) :-
combs(T,T2).
combs([_|T],T2) :-
combs(T,T2).
Da Sie (oder Tropfen) in der Reihenfolge der Liste auswählen, das garantiert Ihnen, dass Sie später nicht a holen wird redecide. Wenn Sie es füttern [a,b,c], wird es nie etwas wie [b,a,c] erzeugen, denn sobald es sich entschieden hat, a zu holen, kann es b nicht hinzufügen und a neu entscheiden.
Laufen ergibt dies:
?- combs([a,b,c],L).
L = [a, b, c] ;
L = [a, b] ;
L = [a, c] ;
L = [a] ;
L = [b, c] ;
L = [b] ;
L = [c] ;
L = [].
Falls Sie es in die andere Richtung erzeugen wollen (mehr von einem Test zum ersten Drop-Elemente haben, anstatt sie hinzufügen, können Sie einfach die rekursive Aussagen tauschen):
combs([],[]).
combs([_|T],T2) :-
combs(T,T2).
combs([H|T],[H|T2]) :-
combs(T,T2).
In diesem Fall wird das Ergebnis sein:
?- combs([a,b,c],L).
L = [] ;
L = [c] ;
L = [b] ;
L = [b, c] ;
L = [a] ;
L = [a, c] ;
L = [a, b] ;
L = [a, b, c].
Da Sie die leere Liste ausschließen möchten, können Sie entweder durch das Hinzufügen eines weiteren Scheck in Ihren Anruf es einfach tun:
combs_without_empty1(LA,LB) :-
combs_without_empty1(LA,LB),
LB \= [].
: wie
?- combs([a,b,c],L),L \= [].
Sie können festlegen, dies in einer Funktion Oder indem Sie die comb/2 Funktion neu schreiben. In diesem Fall besser Sie einen Akkumulator verwenden, die die aktuelle Menge von ausgewählten Elementen zählen:
combs_without_empty(L,C) :-
combs_without_empty(L,0,C).
Die combs_without_empty/3 ist ein bisschen komplizierter. Falls die Liste nur ein Element enthält, sollte überprüft werden, ob N größer als Null ist. Wenn dies der Fall ist, können wir wählen, ob das Element hinzugefügt werden soll oder nicht. Wenn N Null ist, müssen wir es aufnehmen.Also:
combs_without_empty([A],_,[A]).
combs_without_empty([_],N,[]) :-
N > 0.
Wir müssen auch einen rekursiven Teil implementieren, erhöht wird N gegeben wählen wir ein Element:
combs_without_empty([_|T],N,T2) :-
combs_without_empty(T,N,T2).
combs_without_empty([H|T],N,[H|T2]) :-
N1 is N+1,
combs_without_empty(T,N1,T2).
es Putting alles zusammen ergibt:
combs_without_empty(L,C) :-
combs_without_empty(L,0,C).
combs_without_empty([A],_,[A]).
combs_without_empty([_],N,[]) :-
N > 0.
combs_without_empty([_|T],N,T2) :-
combs_without_empty(T,N,T2).
combs_without_empty([H|T],N,[H|T2]) :-
N1 is N+1,
combs_without_empty(T,N1,T2).
Welche produziert:
?- combs_without_empty([a,b,c],L).
L = [c] ;
L = [b, c] ;
L = [b] ;
L = [a, c] ;
L = [a] ;
L = [a, b, c] ;
L = [a, b] ;
false.
Wenn ich die OP Frage direkt zu lesen, es sieht aus wie sie nicht enthalten '[]' als gültige Lösung wollen (?). – lurker
Wie würde ich die leere Liste ausschließen? Diese Antwort war was ich gesucht habe! Ich verstehe auch nicht wirklich, wenn die Funktion Kämme ([_ | T], T2) statt der anderen ausgelöst wird. – Enforcerke
@Enforcerke: In diesem Fall gibt es zwei Optionen, entweder das Prädikat neu schreiben; oder füge einen Haken am Ende hinzu. Ich habe beide kurz besprochen. –
Eine saubere Lösung ohne zusätzliche Prüfungen für leere Liste wäre einfach, leere Listen von den Regeln auszuschließen. Der Basisfall sollte eine einzelne Elementkombination sein:
comb_without_empty([H|_], [H]). % Simple case of one element comb
comb_without_empty([_|T], C) :- % Combinations of the tail w/o head
comb_without_empty(T, C).
comb_without_empty([H|T], [H|C]) :- % Combinations of the tail including head
comb_without_empty(T, C).
| ?- comb_without_empty([a,b,c], L).
L = [a] ? a
L = [b]
L = [c]
L = [b,c]
L = [a,b]
L = [a,c]
L = [a,b,c]
(1 ms) no
| ?-
Können Sie davon ausgehen, dass Sie es nicht eine Liste "[a, b, a]" füttern? –
@GuyCoder: Wenn ich die Frage richtig verstanden habe, handelt es sich um * generierende * Kombinationen. –
@GuyCoder: was ich denke, ist, dass er bedeutet, dass er alle Kombinationen in Einnahme ohne Wiederholung will, wie '[a, a, a]' nicht aufgezählt werden. –