Я написал программу Prolog, чтобы найти все решения для любой ' 8 из 10 кошек, которые ведут обратный отсчет ' числовой последовательности. Я доволен результатом. Тем не менее, решения не являются уникальными. Я пробовал distincts() и reduced() из библиотеки "последовательности решений" . Они не дали уникальных решений.
Проблема проста. у вас есть заданный список из шести чисел [n1, n2, n3, n4, n5, n6] и целевого числа (R). Вычислить R из любой произвольной комбинации из n1 в n6, используя только +, -, *, /. Вам не нужно использовать все номера, но вы можете использовать каждый номер только один раз. Если два решения идентичны, должно быть сгенерировано только одно, а другое отброшено.
Иногда есть эквивалентные результаты с другим расположением. Например:
(100+3)*6*75/50+25
(100+3)*75*6/50+25
У кого-нибудь есть предложения по устранению такой избыточности?
Каждое решение - это вложенные операторы и целые числа. Например +(2,*(4,-(10,5))). Это решение представляет собой несбалансированное двоичное дерево с оператором Arithmeti c для root, а также с одноуровневыми узлами и числами для конечных узлов. Чтобы иметь уникальные решения, никакие два дерева не должны быть эквивалентными.
Код:
:- use_module(library(lists)).
:- use_module(library(solution_sequences)).
solve(L,R,OP) :-
findnsols(10,OP,solve_(L,R,OP),S),
print_solutions(S).
solve_(L,R,OP) :-
distinct(find_op(L,OP)),
R =:= OP.
find_op(L,OP) :-
select(N1,L,Ln),
select(N2,Ln,[]),
N1 > N2,
member(OP,[+(N1,N2), -(N1,N2), *(N1,N2), /(N1,N2), N1, N2]).
find_op(L,OP) :-
select(N,L,Ln),
find_op(Ln,OP_),
OP_ > N,
member(OP,[+(OP_,N), -(OP_,N), *(OP_,N), /(OP_,N), OP_]).
print_solutions([]).
print_solutions([A|B]) :-
format('~w~n',A),
print_solutions(B).
Тест:
solve([25,50,75,100,6,3],952,X)
Результат
(100+3)*6*75/50+25 <- s1
((100+6)*3*75-50)/25 <- s2
(100+3)*75*6/50+25 <- s1
((100+6)*75*3-50)/25 <- s2
(100+3)*75/50*6+25 <- s1
true.
ОБНОВЛЕНИЕ: создание решений с использованием DCG
Ниже приведена попытка создания решений с использованием DCG. Мне удалось создать более исчерпывающий набор решений, чем в предыдущем опубликованном коде. В некотором смысле, использование DCG привело к более правильному и элегантному коду. Однако гораздо труднее «угадать», что делает код.
Проблема избыточных решений все еще сохраняется.
:- use_module(library(lists)).
:- use_module(library(solution_sequences)).
s(L) --> [L].
s(+(L,Ls)) --> [L],s(Ls).
s(*(L,Ls)) --> [L],s(Ls), {L =\= 1, Ls =\= 1, Ls =\= 0}.
s(-(L,Ls)) --> [L],s(Ls), {L =\= Ls, Ls =\= 0}.
s(/(L,Ls)) --> [L],s(Ls), {Ls =\= 1, Ls =\= 0}.
s(-(Ls,L)) --> [L],s(Ls), {L =\= Ls}.
s(/(Ls,L)) --> [L],s(Ls), {L =\= 1, Ls =\=0}.
solution_list([N,H|[]],S) :-
phrase(s(S),[N,H]).
solution_list([N,H|T],S) :-
phrase(s(S),[N,H|T]);
solution_list([H|T],S).
solve(L,R,S) :-
permutation(L,X),
solution_list(X,S),
R =:= S.