Sto cercando un predicato che funziona come questo:sottoinsiemi in Prolog
?- subset([1,2,3], X).
X = [] ;
X = [1] ;
X = [2] ;
X = [3] ;
X = [1, 2] ;
X = [1, 2, 3] ;
X = [2, 3] ;
...
Ho visto alcuni subset implementazioni, ma tutto il lavoro quando si vuole verificare se una lista è un sottoinsieme del un altro, non quando vuoi generare i sottoinsiemi. Qualche idea?
Su http://www.probp.com/publib/listut.html troverete l'implementazione di un predicato chiamato subseq0 che fa quello che si vuole:
subseq0(List, List).
subseq0(List, Rest) :-
subseq1(List, Rest).
subseq1([_|Tail], Rest) :-
subseq0(Tail, Rest).
subseq1([Head|Tail], [Head|Rest]) :-
subseq1(Tail, Rest).
Una breve spiegazione: subseq0(X, Y) controlla se Y è un sottoinsieme sottosequenza di X, mentre subseq1(X, Y) controlli se Y è un corretta sottoinsieme sottosequenza di X.
Poiché la rappresentazione di default di un insieme è una lista con un Elementi iQue, è possibile utilizzare per ottenere tutti i sottoinsiemi, come nel seguente esempio:
?- 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.
Questo genera sottosequenze, non sottoinsiemi. È lo stesso quando si lavora con elenchi ordinati di elementi unici, però. –
Hai praticamente ragione (corretto).Ma perché hai bisogno di ordinare la lista? – Nubok
hai ragione, funzionerà anche quando la lista non è ordinata, solo 'uniq''d. Ma il modo più semplice per ottenere elementi unici è tramite 'sort/2' :) –
Qui va un'implementazione:
subset([], []).
subset([E|Tail], [E|NTail]):-
subset(Tail, NTail).
subset([_|Tail], NTail):-
subset(Tail, NTail).
Essa genererà tutti i sottoinsiemi, anche se non nell'ordine indicato sulla il tuo esempio.
Secondo la richiesta commentatore qui va una spiegazione:
La prima clausola è il caso base. Dichiara che la lista vuota è un sottoinsieme della lista vuota.
La seconda e la terza clausola riguardano la ricorsione. La seconda clausola afferma che se due liste hanno la stessa Testa e la coda della lista di destra è un sottoinsieme della coda della lista di sinistra, allora la lista di destra è un sottoinsieme della lista di sinistra.
La terza clausola afferma che se si salta la testa della lista di sinistra e la lista di destra è un sottoinsieme della coda della lista di sinistra, la lista di destra è un sottoinsieme della lista di sinistra.
La procedura sopra riportata genera set ordinati. Per i set non ordinati si potrebbe utilizzare permutation/3:
unordered_subset(Set, SubSet):-
length(Set, LSet),
between(0,LSet, LSubSet),
length(NSubSet, LSubSet),
permutation(SubSet, NSubSet),
subset(Set, NSubSet).
Puoi spiegare la terza regola? Non capisco del tutto lo scopo. –
@JordanScales: è appena stata aggiunta una spiegazione delle tre clausole ... – gusbro
Funziona solo con set ordinati. Lo prendo? 'sottoinsieme ([2,1], [1,2,3]).' dice no. –
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
Set è una collezione di distinti oggetti per definizione. Una procedura secondaria non dovrebbe interessare sull'ordine degli elementi nel set (negli argomenti). Una soluzione adeguata (SWI Prolog) può apparire come:?
subset(_, []).
subset([X|L], [A|NTail]):-
member(A,[X|L]),
subset(L, NTail),
not(member(A, NTail)).
Per la domanda - sottoinsieme ([1,2,3], E) genererà:
E = [] ;
E = [1] ;
E = [1, 2] ;
E = [1, 2, 3] ;
E = [1, 3] ;
E = [2] ;
E = [2, 3] ;
E = [3] ;
E = [3, 2] ;
false.
auguriamo che contribuiscano !
Dovresti cambiare gli argomenti nel predicato sottoinsiemi (X, Y) in modo che leggiamo naturalmente X è un sottoinsieme di Y, non come hai fatto tu: Y è un sottoinsieme di X. –