Busco un predicado que trabaja como esto:subconjuntos en Prolog
?- subset([1,2,3], X).
X = [] ;
X = [1] ;
X = [2] ;
X = [3] ;
X = [1, 2] ;
X = [1, 2, 3] ;
X = [2, 3] ;
...
He visto algunas implementaciones subset, pero todos ellos trabajan cuando quieren comprobar si una lista es un subconjunto de la otro, no cuando desee generar los subconjuntos. ¿Algunas ideas?
En http://www.probp.com/publib/listut.html encontrará una implementación de un predicado llamado subseq0 que hace lo que quiere:
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 explicación: subseq0(X, Y) comprueba si Y es un subconjunto subsecuencia de X, mientras que subseq1(X, Y) cheques si Y es un adecuada subconjunto subsecuencia de X.
Como la representación de un conjunto predeterminado es una lista con ONU elementos iQue, se puede utilizar para obtener todos los subconjuntos como en el siguiente ejemplo:
?- 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.
Esto genera subsecuencias, no subconjuntos. Sin embargo, eso es lo mismo cuando se trabaja con listas ordenadas de elementos únicos. –
Básicamente tienes razón (lo corrigió).¿Pero por qué necesita que se ordene la lista? – Nubok
tienes razón, también funcionará cuando la lista no esté ordenada, solo 'uniq''d. Pero la forma más fácil de obtener elementos únicos es a través de 'sort/2' :) –
Aquí va una implementación:
subset([], []).
subset([E|Tail], [E|NTail]):-
subset(Tail, NTail).
subset([_|Tail], NTail):-
subset(Tail, NTail).
Se generará todos los subconjuntos, aunque no en el orden que se muestra en tu ejemplo
Según la petición comentarista aquí va una explicación:
La primera cláusula es el caso base. Establece que la lista vacía es un subconjunto de la lista vacía.
La segunda y tercera cláusulas se refieren a la recursividad. La segunda cláusula establece que si dos listas tienen la misma Cabeza y la cola de la lista derecha es un subconjunto de la cola de la lista de la izquierda, entonces la lista de la derecha es un subconjunto de la lista de la izquierda.
La tercera cláusula establece que si saltamos el encabezado de la lista de la izquierda, y la lista de la derecha es un subconjunto de la cola de la lista de la izquierda, la lista de la derecha es un subconjunto de la lista de la izquierda.
El procedimiento que se muestra arriba genera conjuntos ordenados. Para los conjuntos desordenados podría usar permutation/3:
unordered_subset(Set, SubSet):-
length(Set, LSet),
between(0,LSet, LSubSet),
length(NSubSet, LSubSet),
permutation(SubSet, NSubSet),
subset(Set, NSubSet).
¿Podría explicar la tercera regla? No entiendo muy bien su propósito. –
@JordanScales: acaba de agregar una explicación de las tres cláusulas ... – gusbro
Esto solo funciona con conjuntos ordenados ¿Lo tomo? 'subconjunto ([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 es una colección de objetos distintas por definición. Un procedimiento de subconjunto no debería importar sobre el orden de los elementos en el conjunto (en los argumentos). Una solución adecuada (SWI Prolog) puede verse como:?
subset(_, []).
subset([X|L], [A|NTail]):-
member(A,[X|L]),
subset(L, NTail),
not(member(A, NTail)).
Para la pregunta - subconjunto ([1,2,3], E) que va a generar:
E = [] ;
E = [1] ;
E = [1, 2] ;
E = [1, 2, 3] ;
E = [1, 3] ;
E = [2] ;
E = [2, 3] ;
E = [3] ;
E = [3, 2] ;
false.
esperan que ayude a !
Debería cambiar los argumentos en el predicado del subconjunto (X, Y) para que de manera natural leamos que X es un subconjunto de Y, no como lo hizo: Y es un subconjunto de X. –