Teilmengen in Prolog

Ich bin auf der Suche nach einem Prädikat, das funktioniert wie dies:

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

Ich habe gesehen, einige subset Implementierungen, aber Sie funktionieren alle, wenn Sie wollen, um zu überprüfen, ob eine Liste eine Teilmenge der anderen, nicht, wenn Sie möchten, zum erzeugen der Teilmengen. Irgendwelche Ideen?

InformationsquelleAutor der Frage arubox | 2011-02-06

  1. 24

    Geht hier eine Implementierung:

    subset([], []).
subset([E|Tail], [E|NTail]):-
  subset(Tail, NTail).
subset([_|Tail], NTail):-
  subset(Tail, NTail).

    Wird, generiert alle Teilmengen, aber nicht in der Reihenfolge, die auf Ihrem Beispiel.

    Als pro-Kommentator Anfrage geht hier eine Erklärung:

    Die erste Klausel ist der base case. Es besagt, dass die leere Liste ist eine Teilmenge der leeren Liste.

    Die zweiten und Dritten Ziffern Regeln mit Rekursion. Die zweite Klausel besagt, dass, wenn zwei Listen haben den gleichen Kopf und der Schwanz des rechten Liste eine Teilmenge der Schwanz der linken Liste, dann in der rechten Liste eine Teilmenge der in der linken Liste.

    Die Dritte Klausel besagt, dass, wenn wir überspringen den Kopf von der linken Liste, und die Liste rechts ist eine Teilmenge der Schwanz der linken Liste, dann in der rechten Liste eine Teilmenge der in der linken Liste.

    Den Verfahren, die oben gezeigt erzeugt bestellten sets. Für ungeordnete Sätze, die Sie verwenden könnten permutation/3:

    unordered_subset(Set, SubSet):-
  length(Set, LSet),
  between(0,LSet, LSubSet),
  length(NSubSet, LSubSet),
  permutation(SubSet, NSubSet),
  subset(Set, NSubSet).

    InformationsquelleAutor der Antwort gusbro

  2. 8

    Auf http://www.probp.com/publib/listut.html finden Sie eine Implementierung des Prädikats genannt subseq0 das tut, was Sie wollen:

    subseq0(List, List).
subseq0(List, Rest) :-
   subseq1(List, Rest).

subseq1([_|Tail], Rest) :-
   subseq0(Tail, Rest).
subseq1([Head|Tail], [Head|Rest]) :-
   subseq1(Tail, Rest).

    Eine kurze Erklärung: subseq0(X, Y) überprüft, ob Y ist eine Untergruppe Teilfolge von X, während subseq1(X, Y) überprüft, ob Y ist eine richtige Untergruppe Teilfolge von X.

    Da die Standard-Darstellung einer Gruppe ist eine Liste mit eindeutigen Elementen, können Sie es verwenden, um alle Teilmengen wie in der folgenden Beispiel:

    ?- subseq0([1,2,3], X).
X = [1, 2, 3] ;
X = [2, 3] ;
X = [3] ;
X = [] ;
X = [2] ;
X = [1, 3] ;
X = [1] ;
X = [1, 2] ;
false.

    InformationsquelleAutor der Antwort Nubok

  3. 2

    Set ist eine Sammlung von verschiedene Objekte per definition. Eine Teilmenge Verfahren sollte sich keine Gedanken über die Reihenfolge der Elemente im Satz(in der Argumentation). Eine richtige Lösung(swi-prolog) Aussehen könnte:

    subset(_, []).
subset([X|L], [A|NTail]):-
    member(A,[X|L]),    
    subset(L, NTail),
    not(member(A, NTail)).

    Für die Frage ?- Teilmenge([1,2,3], E) erzeugen:

    E = [] ;
E = [1] ;
E = [1, 2] ;
E = [1, 2, 3] ;
E = [1, 3] ;
E = [2] ;
E = [2, 3] ;
E = [3] ;
E = [3, 2] ;
false.

    Hoffe, es wird helfen!

    InformationsquelleAutor der Antwort Volodymyr Ostruk

  4. 0

    können wir auch testen durch löschen der Untergruppe Element aus dem super set.

    % to delete : an item can be deleted it its in the head or in the tail of a list
delete(I,[I|L],L).
delete(I,[H|L],[H|NL]) :- delete(I,L,NL).
% an [] is an item of an set.A set is a subset of we can recursively delete its head item from the super set.
subset(_,[]).
subset(S,[I|SS]) :- delete(I,S,S1), subset(S1,SS).

    Beispiel:

    subset([a,b,c],S).
S = []
S = [a]
S = [a, b]
S = [a, b, c]
S = [a, c]
S = [a, c, b]
S = [b]
S = [b, a]
S = [b, a, c]
S = [b, c]
S = [b, c, a]
S = [c]
S = [c, a]
S = [c, a, b]
S = [c, b]
S = [c, b, a] 

    subset([a,b,a,d,e],[a,e]).
1true

    InformationsquelleAutor der Antwort durga

  5. -2
    append([],L,L).

append([H|T],L,[H|L1]):-append(T,L,L1).


subset([X|T],[X|L]) :-subset(T,L).

subset([X|T],[G|L]) :-subset([X],L),append(L2,[X|L3],[G|L]),append(L2,L3,L4),subset(T,L4).

subset([],_).

----------------------------------------------
?- subset([1,2],[1,2]).

yes

?- subset([1,2],[2,1]).

yes

?- subset([1,1],[1,2]).

no

?- subset(D,[1,2]).

D = [1,2] ;

D = [1] ;

D = [2,1] ;

D = [2] ;

D = '[]' ;

no

    InformationsquelleAutor der Antwort

Schreibe einen Kommentar