Definición más compacta
Dado word/1,
word(W) :-
abs(ABs),
ABs = W.
abs([]).
abs([AB|ABs]) :-
abs(ABs),
ab(AB).
ab(a).
ab(b).
?- word(W).
W = []
; W = [a]
; W = [b]
; W = [a,a]
; W = [b,a]
; W = [a,b]
; W = [b,b]
; W = [a,a,a]
; W = [b,a,a]
; W = [a,b,a]
; W = [b,b,a]
; W = [a,a,b]
; W = [b,a,b]
; W = [a,b,b]
; W = [b,b,b]
; W = [a,a,a,a]
...
¿Cómo se ve una definición más compacta de word/1, de lo contrario idéntica terminación w.r.t. y el conjunto de soluciones, equidad, con las siguientes restricciones:
No se usan built-ins como
(=)/2.No se usan construcciones de control como
(',')/2o(;)/2, ocall/1.Usa un hecho, una regla recursiva y una regla para
word/1.
Tal vez más simple es pedir los términos F1 ... F4 en:
word(W) :-
p(F1).
p(F2).
p(F3) :-
p(F4).
Para el registro: La propiedad explotada aquí está estrechamente relacionada con la indecibilidad de la terminación de una sola cláusula binaria. La alabanza va a:
[11] Philippe Devienne, Patrick Lebègue, Jean-Christophe Routier y Jörg Würtz. Una cláusula binaria de cuerno es suficiente STACS ' 94 .7 answers
La solución que he encontrado es:
word(W) :-
p([[]|Ls], Ls, W).
p([W|_], _, W).
p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :-
p(Ws, Ls, W).
Ejemplo de consulta y respuesta:
?- word(W). W = [] ; W = [a] ; W = [b] ; W = [a, a] ; W = [b, a] ; W = [a, b] ; W = [b, b] ; W = [a, a, a] ; W = [b, a, a] ; W = [a, b, a] ; W = [b, b, a] ; W = [a, a, b] ; W = [b, a, b] ; W = [a, b, b] ; W = [b, b, b] ; W = [a, a, a, a] ; W = [b, a, a, a] ; etc.
Estoy usando una lista de diferencias para materializar gradualmente las soluciones que quiero que el nivel superior informe.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-02-23 16:14:56
Está bien, así que no es una respuesta todavía.
Lo más cercano que tuve fue :
s_s1([],[a]).
s_s1([b|T],[a|T]).
s_s1([a|T],[b|T2]):-
s_s1(T,T2).
word([]).
word(W2):-
word(W),
s_s1(W,W2).
Que no cumple los criterios ni da las soluciones correctas!
Así que a continuación pensé que podríamos intentar usar prolog para encontrar la respuesta.. La estructura está dada por lo que necesitamos buscar los args..
%First define the first 16 correct solutions..
correct_sols(X):-
X=[
[],
[a],
[b],
[a,a],
[b,a],
[a,b],
[b,b],
[a,a,a],
[b,a,a],
[a,b,a],
[b,b,a],
[a,a,b],
[b,a,b],
[a,b,b],
[b,b,b],
[a,a,a,a]
].
%Then a mi
provable(true, _) :- !.
provable((G1,G2), Defs) :- !,
provable(G1, Defs),
provable(G2, Defs).
provable(BI, _) :-
predicate_property(BI, built_in),
!,
call(BI).
provable(Goal, Defs) :-
member(Def, Defs),
copy_term(Def, Goal-Body),
provable(Body, Defs).
%From 4 Vars find 16 solutions to word(X)
vars_16sols(Vars,List):-
Vars =[Args,Args0,Args1,Argsx],
findnsols(16,X,provable(word(X),[
a(Args)-true,
a(Args0)-a(Args1),
word(X)-a(Argsx)]
),List).
%Evaluate the score, for the solutions found how many match correct
evaluate_score(Solutions,Score):-
correct_sols(C),
maplist(correct_test_tf,C,Solutions,TrueFalse),
findall(_,member(true,TrueFalse),Matches),
length(Matches,Score).
%The main search, give a form for the starting 4 arguments, if they
match all 16 correct stop.
startingargs_solution(Start,Sol):-
vars_16sols(Start,SolsStart),
evaluate_score(SolsStart,Score),
Score =16,
SolsStart=Sol.
%Othewise refine args, and try again.
startingargs_solution(Start,Sol):-
vars_16sols(Start,SolsStart),
evaluate_score(SolsStart,Score),
Score <16,
start_refined(Start,Refined),
startingargs_solution(Refined,Sol).
Todavía necesitaríamos definir:
- correct_test_tf / 3
- start_refined / 2 con algunas restricciones, como el tamaño de los términos para args (debe ser razonable para ser una 'definición compacta', y qué cosas deben incluirse, es decir, al menos
ayben algún lugar y probablemente[].
Claramente no está terminado y no estoy seguro de si será posible hacer esto, pero pensé que publicaría una respuesta para ver lo que la gente tiene que decir.. La búsqueda es ingenua en este momento!
Esto es solo probar las primeras 16 soluciones, pero tal vez eso sea adecuado para obtener una respuesta correcta..
También tal vez esto es más difícil entonces resolver la pregunta sobre su ¡propia!
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-02-17 09:33:44
Mi más cercano todavía.
unfold20([], []).
unfold20([H|T], [[a|H], [b|H]|L]) :-
unfold20(T, L).
member20(X, [X|_]).
member20(X, [_|Tail]) :-
member20(X, Tail).
swap20(R,R) :-
write('swap20 R: '),write(R),nl.
swap20(In,L) :-
write('swap20 In: '),write(In),nl,
unfold20(In,L),
swap20(L,_),
write('swap20 L: '),write(L),nl.
word20(W) :-
swap20([[]],L),
write('word20 L: '),write(L),nl,
member20(W,L),
write('word20 W: '),write(W),nl.
?- word20(X).
swap20 R: [[]]
word20 L: [[]]
word20 W: []
X = [] ;
swap20 In: [[]]
swap20 R: [[a],[b]]
swap20 L: [[a],[b]]
word20 L: [[a],[b]]
word20 W: [a]
X = [a] ;
word20 W: [b]
X = [b] ;
swap20 In: [[a],[b]]
swap20 R: [[a,a],[b,a],[a,b],[b,b]]
swap20 L: [[a,a],[b,a],[a,b],[b,b]]
swap20 L: [[a],[b]]
word20 L: [[a],[b]]
word20 W: [a]
X = [a] ;
word20 W: [b]
X = [b] ;
swap20 In: [[a,a],[b,a],[a,b],[b,b]]
swap20 R: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]]
swap20 L: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]]
swap20 L: [[a,a],[b,a],[a,b],[b,b]]
swap20 L: [[a],[b]]
word20 L: [[a],[b]]
word20 W: [a]
X = [a] ;
word20 W: [b]
X = [b] ;
swap20 In: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]]
swap20 R: [[a,a,a,a],[b,a,a,a],[a,b,a,a],[b,b,a,a],[a,a,b,a],[b,a,b,a],[a,b,b,a],[b,b,b,a],[a,a,a,b],[b,a,a,b],[a,b,a,b],[b,b,a,b],[a,a,b,b],[b,a,b,b],[a,b,b,b],[b,b,b,b]]
swap20 L: [[a,a,a,a],[b,a,a,a],[a,b,a,a],[b,b,a,a],[a,a,b,a],[b,a,b,a],[a,b,b,a],[b,b,b,a],[a,a,a,b],[b,a,a,b],[a,b,a,b],[b,b,a,b],[a,a,b,b],[b,a,b,b],[a,b,b,b],[b,b,b,b]]
swap20 L: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]]
swap20 L: [[a,a],[b,a],[a,b],[b,b]]
swap20 L: [[a],[b]]
word20 L: [[a],[b]]
word20 W: [a]
X = [a]
Si miran verán que no hay uso de ; que estoy seguro es un problema que algunas personas están teniendo. Además, todas las reglas son lo suficientemente simples como para que puedan plegarse a los requisitos mediante el uso de argumentos adicionales. por ejemplo, unfold(A,B) se convertiría en unfold(A,B,C,D) o una variación.
El problema con esta versión es que obtengo las respuestas correctas a medida que avanza la evaluación, solo es volver a el nivel superior.
Por ejemplo
swap20 L: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]]
swap20 L: [[a,a],[b,a],[a,b],[b,b]]
swap20 L: [[a],[b]]
Seguiré trabajando en esto antes de la línea muerta, pero si alguien es capaz de usar lo que tengo aquí, me quito el sombrero ante ellos, solo le pido que dé crédito si alguna parte de esto le ayudó a obtener la respuesta.
El predicado unfold se basa en esto ASÍ que respuesta. Credit to salva
member es un viejo amigo. Observe que comienza con [[]] y no [].
swap Yo creé este predicado. He intercambiado trabajando para una variación diferente, pero la variación falla por una razón diferente.
Suplemento
Salida del depurador de la respuesta de mat
Miré La respuesta de Mat más de cerca con un depurador porque podría contener la respuesta a un problema similar donde puedo generar las respuestas pero no devolverlas independientemente a la Parte Superior.
Respuesta de Mat copiada aquí para referencia.
p([W|_], _, W).
p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :-
p(Ws, Ls, W).
word(W) :-
p([[]|Ls], Ls, W).
La parte de interés está muy a la derecha como comentarios. Lo haría sugiera que copie desde aquí y desde el pasado en una aplicación que le permita ver toda la línea sin envolver ni ocultar.
La columna de la izquierda se creó con SWI-Prolog ejecutando la consulta con trace y los comentarios de la derecha se crearon ejecutando la consulta con gtrace y copiando a mano los valores y anotando el nivel de sangría.
?- word(W).
Call: (8) word(_822) ? creep % word(W) :-
Call: (9) p([[]|_1010], _1010, _822) ? creep % p([[]|Ls], Ls, W).
Exit: (9) p([[]|_1010], _1010, []) ? creep % p([W|_], _, W). % W = []
Exit: (8) word([]) ? creep % p([[]|Ls], Ls, W). % W = []
W = [] ;
Redo: (9) p([[]|_1010], _1010, _822) ? creep % p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :- % W0 = [] Ws = [[a],[b]|Ls]
Call: (10) p([[a], [b]|_1028], _1028, _822) ? creep % p(Ws, Ls, W). % W0 = [] Ws = [[a],[b]|Ls]
Exit: (10) p([[a], [b]|_1028], _1028, [a]) ? creep % p([W|_], _, W). % W = [a]
Exit: (9) p([[], [a], [b]|_1028], [[a], [b]|_1028], [a]) ? creep % p(Ws, Ls, W). % W = [a] W0 = [] Ws = [[a],[b]|Ls]
Exit: (8) word([a]) ? creep % p([[]|Ls], Ls, W). % W = [a] Ls = [[a],[b]|_2312]
W = [a] ;
Redo: (10) p([[a], [b]|_1028], _1028, _822) ? creep % p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :- % W0 = [a] Ws = [ [b],[a,a],[b,a]|Ls]
Call: (11) p([[b], [a, a], [b, a]|_1052], _1052, _822) ? creep % p(Ws, Ls, W). % W0 = [a] Ws = [ [b],[a,a],[b,a]|Ls]
Exit: (11) p([[b], [a, a], [b, a]|_1052], _1052, [b]) ? creep % p([W|_], _, W). % W = [b]
Exit: (10) p([[a], [b], [a, a], [b, a]|_1052], [[a, a], [b, a]|_1052], [b]) ? creep % p(Ws, Ls, W). % W = [b] W0 = [a] Ws = [ [b],[a,a],[b,a]|Ls]
Exit: (9) p([[], [a], [b], [a, a], [b, a]|_1052], [[a], [b], [a, a], [b, a]|_1052], [b]) ? creep % p(Ws, Ls, W). % W = [b] W0 = [] Ws = [[a],[b],[a,a],[b,a]|_2324] Ls = [ [a,a],[b,a]|_2324]
Exit: (8) word([b]) ? creep % p([[]|Ls], Ls, W). % W = [b] Ls = [[a],[b],[a,a],[b,a]|_2324]
W = [b] .
Redo: (11) p([[b], [a, a], [b, a]|_1052], _1052, _822) ? creep % p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :- % W0 = [b] Ws = [ [a,a],[b,a],[a,b],[b,b]|Ls]
Call: (12) p([[a, a], [b, a], [a, b], [b, b]|_1076], _1076, _822) ? creep % p(Ws, Ls, W). % W0 = [b] Ws = [ [a,a],[b,a],[a,b],[b,b]|Ls]
Exit: (12) p([[a, a], [b, a], [a, b], [b, b]|_1076], _1076, [a, a]) ? creep % p([W|_], _, W). % W = [a,a]
Exit: (11) p([[b], [a, a], [b, a], [a, b], [b, b]|_1076], [[a, b], [b, b]|_1076], [a, a]) ? creep % p(Ws, Ls, W). % W = [a,a] W0 = [b] Ws = [ [a,a],[b,a],[a,b],[b,b]|Ls]
Exit: (10) p([[a], [b], [a, a], [b, a], [a, b], [b, b]|_1076], [[a, a], [b, a], [a, b], [b, b]|_1076], [a, a]) ? creep % p(Ws, Ls, W). % W = [a,a] W0 = [a] Ws = [ [b],[a,a],[b,a],[a,b],[b,b]|_2348] Ls = [ [a,b],[b,b]|_2348]
Exit: (9) p([[], [a], [b], [a, a], [b, a], [a, b], [b|...]|_1076], [[a], [b], [a, a], [b, a], [a, b], [b, b]|_1076], [a, a]) ? creep % p(Ws, Ls, W). % W = [a,a] W0 = [] Ws = [[a],[b],[a,a],[b,a],[a,b],[b,b]|_2348] Ls = [ [a,a],[b,a],[a,b],[b,b]|_2348]
Exit: (8) word([a, a]) ? creep % p([[]|Ls], Ls, W). % W = [a,a] Ls = [[a],[b],[a,a],[b,a],[a,b],[b,b]|_2348]
W = [a, a] ;
Redo: (12) p([[a, a], [b, a], [a, b], [b, b]|_1076], _1076, _822) ? creep
Call: (13) p([[b, a], [a, b], [b, b], [a, a, a], [b, a, a]|_1100], _1100, _822) ? creep % p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :- % W0 = [a,a] Ws = [ [b,a],[a,b],[b,b],[a,a,a],[b,a,a]|Ls]
Exit: (13) p([[b, a], [a, b], [b, b], [a, a, a], [b, a, a]|_1100], _1100, [b, a]) ? creep % p(Ws, Ls, W). % W0 = [a,a] Ws = [ [b,a],[a,b],[b,b],[a,a,a],[b,a,a]|Ls]
Exit: (12) p([[a, a], [b, a], [a, b], [b, b], [a, a, a], [b, a|...]|_1100], [[a, a, a], [b, a, a]|_1100], [b, a]) ? creep % p([W|_], _, W). % W = [b,a]
Exit: (11) p([[b], [a, a], [b, a], [a, b], [b, b], [a, a|...], [b|...]|_1100], [[a, b], [b, b], [a, a, a], [b, a, a]|_1100], [b, a]) ? creep % p(Ws, Ls, W). % W = [b,a] W0 = [a,a] Ws = [ [b,a],[a,b],[b,b],[a,a,a],[b,a,a]|Ls]
Exit: (10) p([[a], [b], [a, a], [b, a], [a, b], [b, b], [a|...], [...|...]|...], [[a, a], [b, a], [a, b], [b, b], [a, a, a], [b, a|...]|_1100], [b, a]) ? creep % p(Ws, Ls, W). % W = [b,a] W0 = [b] Ws = [ [a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372] Ls = [ [a,a,a],[b,a,a]|_2372]
Exit: (9) p([[], [a], [b], [a, a], [b, a], [a, b], [b|...], [...|...]|...], [[a], [b], [a, a], [b, a], [a, b], [b, b], [a|...], [...|...]|...], [b, a]) ? creep % p(Ws, Ls, W). % W = [b,a] W0 = [a] Ws = [ [b],[a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372] Ls = [ [a,b],[b,b],[a,a,a],[b,a,a]|_2372]
Exit: (8) word([b, a]) ? creep % p(Ws, Ls, W). % W = [b,a] W0 = [] Ws = [[a],[b],[a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372] Ls = [ [a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372]
W = [b, a] ; % p([[]|Ls], Ls, W). % W = [b,a] Ls = [[a],[b],[a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372]
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:02:02
Normalmente publicaría estos como una sola respuesta, pero @false me pidió que los mantuviera separados.
Si lees mis comentarios y respuestas verás que era consciente de que tenía que pasar el resultado de una iteración de nuevo a la siguiente iteración. Lo que me dio una idea de eso fue usar un predicado de producto cruzado que encontré en
"El arte de Prolog" por Richard A. O'Keefe pg. 243
Si usted es serio acerca de aprender Prolog, el libro es una necesidad tener.
Para citar el Prefacio
Hay un montón de libros Prolog introductorios alrededor. Este no es uno de ellos. Piense en ello como"segundos pasos en Prolog". Si ya tiene lea uno de los libros introductorios, si ha tomado una introducción curso sobre Prolog, si ha escrito ore o dos programas Prolog, y si se está preguntando por qué todavía es difícil escribir un buen Prolog programas, este libro está destinado a ayudarle. El propósito del libro es para mostrarte cómo puedes escribir programas Prolog que funcionen, que no tomar una cantidad irrazonable de tiempo, y que son lo suficientemente limpio para mostrar por tus amigos.
Aquí hay una ligera variación que usé para una variación que no funcionó.
combine(X,Y,[X,Y]).
product(P,Xs,Ys,PXYs) :-
product1(Xs,Ys,PXYs,P).
product1([],_,[],_).
product1([X|Xs],Ys,PXYs0,P) :-
product1(Ys,X,P,PXYs0,PXYs1),
product1(Xs,Ys,PXYs1,P).
product1([],_,_) --> [].
product1([Y|Ys],X,P) -->
{
call(P,X,Y,PXY)
},
[PXY],
product1(Ys,X,P).
?- product(combine,[a,b],[a,b],R).
R = [[a, a], [a, b], [b, a], [b, b]].
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-10-26 11:24:38
Así que para aclarar, la solución prevista es una instancia del siguiente esquema?
fact(Args).
recursive_rule(Args0) :-
recursive_rule(Args1).
word(W) :-
recursive_rule(Args).
Donde cada aparición de una variable Args representa cero o más términos y presumiblemente (pero no necesariamente) fact y recursive_rule son en realidad el mismo funtor?
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-02-16 16:45:43
Con las sugerencias de Guy coder esto está más cerca?
unfold([], []).
unfold([H|T], [[a|H], [b|H]|L]) :-
unfold(T, L).
ab([], [[]]).
ab([_|N1],L):-
ab(N1, L1),
unfold(L1, L).
word(X):-
length(List,_),
ab(List,Values),
member(X,Values).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-02-23 15:50:41
No es una solución, sino una visión hacia una solución.
Esto comenzó con el uso de DCG
abs4 --> [].
abs4 --> abs4, ([a] | [b]).
?- phrase(abs4,X).
X = [] ;
X = [a] ;
X = [b] ;
X = [a, a] ;
X = [a, b] ;
X = [b, a] ;
X = [b, b] ;
X = [a, a, a] ;
X = [a, a, b] ;
X = [a, b, a] ;
X = [a, b, b] ;
X = [b, a, a] ;
X = [b, a, b] ;
X = [b, b, a] ;
X = [b, b, b] ;
X = [a, a, a, a] ;
X = [a, a, a, b] ;
Luego mirando el listado
?- listing(abs4).
abs4(A, A).
abs4(A, C) :-
abs4(A, B),
( B=[a|C]
; B=[b|C]
).
Y usando member para eliminar el ;.
word5(W) :-
abs5(W,[]).
abs5(A, A).
abs5(A, C) :-
abs5(A, [D|C]),
member5(D,[a,b]).
member5(X, [X|_]).
member5(X, [_|Tail]) :-
member5(X, Tail).
?- word5(X).
X = [] ;
X = [a] ;
X = [b] ;
X = [a, a] ;
X = [a, b] ;
X = [b, a] ;
X = [b, b] ;
X = [a, a, a] ;
X = [a, a, b] ;
X = [a, b, a] ;
X = [a, b, b] ;
X = [b, a, a]
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-03-30 21:02:25