à Prolog

Question

Sous-ensembles

Je cherche un prédicat qui fonctionne comme ceci:

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

J'ai vu quelques subset mises en œuvre, mais ils travaillent tous lorsque vous souhaitez vérifier si une liste est un sous-ensemble de la un autre, pas quand vous voulez générer les sous-ensembles. Des idées?

Answer 1

Sur http://www.probp.com/publib/listut.html vous trouverez une implémentation d'un prédicat appelé subseq0 qui fait ce que vous voulez:

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

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

Une brève explication: subseq0(X, Y) vérifie si Y est un sous-ensemble-séquence de X, tandis que subseq1(X, Y) contrôles si Y est un bon sous-ensemble de X. séquence

Depuis la représentation par défaut d'un ensemble est une liste avec un éléments ique, vous pouvez l'utiliser pour obtenir tous les sous-ensembles comme dans l'exemple suivant:

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

Answer 2

va ici une mise en œuvre:

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

Il génère tous les sous-ensembles, mais pas dans l'ordre indiqué sur votre exemple.

Selon la demande de commentateur va ici une explication:

La première clause est le cas de base. Il indique que la liste vide est un sous-ensemble de la liste vide.

Les deuxième et troisième clauses traitent de la récursivité. La deuxième clause stipule que si deux listes ont la même tête et la queue de la liste de droite est un sous-ensemble de la queue de la liste de gauche, alors la liste de droite est un sous-ensemble de la liste de gauche. La troisième clause stipule que si nous ignorons la tête de la liste de gauche et que la liste de droite est un sous-ensemble de la queue de la liste de gauche, la liste de droite est un sous-ensemble de la liste de gauche.

La procédure ci-dessus génère des ensembles ordonnés. Pour les ensembles désordonnées vous pouvez utiliser permutation/3:

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

Answer 3

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 

Answer 4

Set est une collection d'objets distincts par définition. Une procédure de sous-ensemble ne doit pas se préoccuper de sur l'ordre des éléments dans l'ensemble (dans les arguments). Une solution appropriée (SWI prolog) peut ressembler à:

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

Pour la question - sous-ensemble ([1,2,3], E) il va générer:

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

espère que cela aidera !