1

Estoy teniendo problemas con el siguiente predicado:

partir(Todo, Parte1, Parte2)

que se verifica si Parte1 y Parte2 son dos subsecuencias no vacías que concatenadas forman la secuencia Todo. Una posible traza sería

[a,b,c,d] se parte como [a] [b,c,d]; [a,b] [c,d]; [a,b,c] [d].

El orden tiene que prevalecer y no puede haber una lista vacía.

Lo estoy implementando como el predicado concatena, pero no logro evitar que en las soluciones por back tracking devuelva listas vacías.

partir([],[],[]).
partir(Ys,Ys,[]).
partir([X|Xs],Ys,[X|Zs]):-partir(Xs,Ys,Zs).
2
  • ¿ya intentaste metiéndole cortes? Ya sabes el símbolo de ! Commented el 18 may. 2021 a las 13:29
  • Aun no lo he probado, también porque no sabría muy bien donde meter el corte Commented el 18 may. 2021 a las 13:55

2 respuestas 2

0

Para tu problema se me ocurrió primero declarar que no quieres listas vacías.

Esto lo hago usando la función length, y haciendo una aserción sobre el tamaño.

Adicionalmente ví que a Ys no le hacías nada , así que agregué otro predicado y para sortear un poco los casos en que Ys pudiera valer [].

partir(Ys,Ys,[]).
partir([],[],[]).
partir([X|Xs],Ys,[X|Zs]):-
    partir(Xs,Ys,Zs)
    ,length([X|Xs],N)
    ,N>1
    .

partir([X|Xs],[X|Ys],Zs):-
    partir(Xs,Zs,Ys)
    ,length([X|Xs],N)
    ,N>1
    .

La salida será:

partir([1,2,3,4],X,Y).

X = [1, 2, 3, 4], Y = [] ;

X = [2, 3, 4], Y = [1] ;

X = [3, 4], Y = [1, 2] ;

X = [4], Y = [1, 2, 3] ;

X = [3], Y = [1, 2, 4] ;

X = [2], Y = [1, 3, 4] ;

X = [2, 3], Y = [1, 4] ;

X = [2, 4], Y = [1, 3] ;

X = [1], Y = [2, 3, 4] ;

X = [1, 2], Y = [3, 4] ;

X = [1, 2, 3], Y = [4] ;

X = [1, 2, 4], Y = [3] ;

X = [1, 3, 4], Y = [2] ;

X = [1, 4], Y = [2, 3] ;

X = [1, 3], Y = [2, 4] ;

false.

0

Primero notar que el procedimiento que indicas no verifica que Parte1 y Parte2 concatenados forman Todo, por ejemplo con esta consulta (la segunda solución es incorrecta):

?- Todo=[a,b], partir(Todo, Parte1, Parte2).
Todo = Parte1, Parte1 = [a, b],
Parte2 = [] ;
Todo = [a, b],
Parte1 = [b],
Parte2 = [a] ;
Todo = Parte2, Parte2 = [a, b],
Parte1 = [] ;
Todo = Parte2, Parte2 = [a, b],
Parte1 = [].

Podemos escribir el procedimiento recursivo:

%partir(Todo, Parte1, Parte2)

partir([Y,Z|Zs], [Y], [Z|Zs]).   % paso base
partir([Y|Xs], [Y|Ys], Zs):-     % paso recursivo
  partir(Xs,Ys,Zs).

dónde en el paso base declaramos que tanto Parte1 como Parte2 tienen un único elemento, y Todo es la concatenación de los mismos.

Luego en el paso recursivo vamos tomando 1 elemento de Parte1 y lo colocamos al comienzo de la lista Todo y hacemos la llamada recursiva.

Ejemplo:

?- partir([a,b,c,d], Parte1, Parte2).
Parte1 = [a],
Parte2 = [b, c, d] ;
Parte1 = [a, b],
Parte2 = [c, d] ;
Parte1 = [a, b, c],
Parte2 = [d] ;
false.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.