Alle Teilmengen von Listen mit k Elementen in Prolog

Question

Bitte helfen Sie mir, dieses Problem zu lösen:

Teilmenge(N, [1,2,3], L).

wenn N=2, möchte ich, dass das Ergebnis ist, dass:

[1,2];

[2,1];

[1,3];

[3,1];

[2,3];

[3,2];

(in beliebiger Reihenfolge)

Answer 1

Ich schreibe diese Lösung um: (basierend auf: Permutierte Kombinationen der Elemente einer Liste - Prolog )

subset(N, InList, Out) :-
    splitSet(InList,_,SubList),
    permutation(SubList,Out),
    length(Out, N).

splitSet([ ],[ ],[ ]).
splitSet([H|T],[H|L],R) :-
    splitSet(T,L,R).
splitSet([H|T],L,[H|R]) :-
    splitSet(T,L,R).

Das Ergebnis (getestet in SWI-Prolog):

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

Answer 2

Nun, Ihr Basisfall ist trivial:

subset(0,Lst,[]).

Wenn N>0, haben Sie 2 Möglichkeiten, was mit dem ersten Element von Lst zu tun ist:

1. Sie können sie ignorieren und Ihre Teilmenge in den Resten von Lst suchen
2. Sie können es in Ihre Teilmenge aufnehmen, indem Sie es zu dem hinzufügen, was Sie für eine 1 kleinere Teilmenge dessen, was von Lst übrig bleibt, erhalten.

Man könnte meinen, dass man sich Sorgen machen muss, dass Lst zu kurz ist (oder N zu groß ist: das ist dasselbe), aber wenn man das oben genannte richtig kodiert hat, sollte es für einen erledigt sein.

Puh, das reicht für den Anfang.