Ich versuche, eine Regel zu erstellen, um festzustellen, ob eine Liste eine Unterliste der Größe n einer anderen Liste ist.

isSubgroup/3
isSubgroup(+Subgroup, +Group, +N)

Zum Beispiel würde isSubgroup([1, 2, 4], [1, 2, 3, 4, 5], 3) True zurückgeben

isSubgroup([4, 2, 1], [1, 2, 3, 4, 5], 3) würde jedoch False zurückgeben (aufgrund der unterschiedlichen Reihenfolge)

Ich dachte daran, für jedes Mitglied der Untergruppe zu prüfen, ob es ein Mitglied der großen Gruppe ist oder nicht, aber das würde die Reihenfolge ignorieren.

Ist die Idee machbar?

2
Alon 18 Jän. 2019 im 17:26

3 Antworten

Beste Antwort

Wie @WillemVanOnsem vorschlug, eine induktive Lösung:

subGroups([], []).

subGroups([X|Xs], [X|Ys]):-
    subGroups(Xs, Ys).

subGroups(Xs, [_|Ys]):-
    subGroups(Xs, Ys).

subGroupsN(Options, N, Solution) :-
    length(Solution, N),
    subGroups(Solution, Options).
2
Alon 19 Jän. 2019 im 09:26

Versuchen Sie wirklich, eine induktive Beziehung zu schreiben. In der Zwischenzeit kann die Bibliothek (yall) in Verbindung mit der Bibliothek (apply) einen Liner bilden:

isSubgroup(S,G,N) :- length(S,N),
    foldl({G}/[E,P,X]>>(nth1(X,G,E),X>=P),S,1,_F).
2
CapelliC 18 Jän. 2019 im 15:07

Wir können diese Vorhersage durch eine induktive Definition definieren. Ein Subgroup ist eine Untergruppe von Group, wenn:

  1. das Subgroup ist eine leere Liste;
  2. Das erste Element von Subgroup ist dasselbe wie das erste Element von Group, und der Rest von Subgroup ist eine Untergruppe des Restes von Group.
  3. Das Subgroup ist eine Untergruppe des Restes des Group.

Wir müssen N entsprechend aktualisieren, sodass die Länge 0 beträgt, wenn Subgroup leer ist:

isSubgroup([], _, 0).              %% (1)
isSubgroup([H|TS], [H|TG], N) :-   %% (2)
    N1 is N-1,
    isSubgroup(TS, TG, N1).
isSubgroup(S, [_|TG], N) :-        %% (3)
    isSubgroup(S, TG, N).

Das Obige führt jedoch zu doppelten Wahrheiten für dieselbe Untergruppe . Dies liegt an der Tatsache, dass wir das Prädikat auf verschiedene Weise erfüllen können. Zum Beispiel, wenn wir anrufen:

isSubgroup([], [1,2], 0).

Dann ist es durch die Tatsache (1) erfüllt, aber die letzte Klausel (3) nennt dies auch mit isSubgroup([], [1], 0)., die dann durch die Tatsache (1) usw. erfüllt wird.

Wir können dies vermeiden, indem wir die letzte Klausel restriktiver gestalten:

isSubgroup([], _, 0).              %% (1)
isSubgroup([H|TS], [H|TG], N) :-   %% (2)
    N1 is N-1,
    isSubgroup(TS, TG, N1).
isSubgroup([HS|TS], [_|TG], N) :-  %% (3)
    isSubgroup([HS|TS], TG, N).

Das Obige funktioniert für die angegebenen "Richtungen" (alle Argumente sollten begründet sein, sind "Eingabe"). Aber normalerweise möchte man ein Prädikat auch in andere Richtungen verwenden. Wir können eine Version implementieren, die grundsätzlich funktioniert, wenn wir Argumente auch als "Ausgabe" verwenden und dennoch die Tail-Call-Optimierung (TCO) verwenden:

isSubgroup(S, G, N) :-
    isSubgroup(S, G, 0, N).

isSubgroup([], _, L, L).              %% (1)
isSubgroup([H|TS], [H|TG], L, N) :-   %% (2)
    L1 is L+1,
    isSubgroup(TS, TG, L1, N).
isSubgroup([HS|TS], [_|TG], L, N) :-  %% (3)
    isSubgroup([HS|TS], TG, L, N).

Beispielsweise:

?- isSubgroup([1,4,2], G, N).
G = [1, 4, 2|_2974],
N = 3 ;
G = [1, 4, _2972, 2|_2986],
N = 3 ;
G = [1, 4, _2972, _2984, 2|_2998],
N = 3 ;
G = [1, 4, _2972, _2984, _2996, 2|_3010],
N = 3 .

Hier kann Prolog somit Gruppen vorschlagen, für die [1,4,2] eine Untergruppe ist, und es kann die Länge N der Untergruppe bestimmen.

Wir können auch in die entgegengesetzte Richtung abfragen:

?- isSubgroup(S, [1,4,2], N).
S = [],
N = 0 ;
S = [1],
N = 1 ;
S = [1, 4],
N = 2 ;
S = [1, 4, 2],
N = 3 ;
S = [1, 2],
N = 2 ;
S = [4],
N = 1 ;
S = [4, 2],
N = 2 ;
S = [2],
N = 1 ;
false.

Prolog kann für eine bestimmte Gruppe [1,4,2] alle möglichen Untergruppen zusammen mit N der Länge dieser Untergruppe vollständig auflisten.

0
Willem Van Onsem 19 Jän. 2019 im 15:40