У меня есть частичное решение, которое я опишу здесь, и, надеюсь, оно заставит вас двигаться, и вы сможете найти полное решение.
Первый инструмент, который вам нужен, - это возможность создавать выражения:
build_expr(X, Y, X+Y).
build_expr(X, Y, X*Y).
build_expr(X, Y, X-Y).
build_expr(X, Y, X/Y).
Это определяет build_expr/3, который принимает две переменные или выражения и создает новое выражение.Вот как мы собираемся переставлять операторов.Теперь нам нужен способ обработки списков, поэтому давайте определим build_expr/2, который работает со списком сразу:
% base case: we are down to two variables and call build_expr/3
build_expr([X,Y], Expr) :- build_expr(X, Y, Expr).
% inductive case: make the expression on the rest of the list and combine
% with the leading variable here
build_expr([X|Rest], Expr) :-
build_expr(Rest, Expr0),
build_expr(X, Expr0, Expr).
Давайте получим несколько решений, чтобы понять, что он делает:
3 ?- build_expr([10,10,10,10],X).
X = 10+(10+(10+10)) ;
X = 10*(10+(10+10)) ;
X = 10-(10+(10+10)) ;
X = 10/(10+(10+10)) ;
X = 10+10*(10+10) ;
X = 10*(10*(10+10)) ;
X = 10-10*(10+10) ;
X = 10/(10*(10+10)) ;
X = 10+(10-(10+10)) ;
X = 10*(10-(10+10)) ;
X = 10-(10-(10+10)) ;
X = 10/(10-(10+10)) ;
Это выглядит довольно хорошо для меня.Но, как я уже сказал, я создаю только правильное дерево.Вам придется изменить или заменить build_expr/2, чтобы получить другие фигуры, если они действительно имеют значение (что, я не уверен, что они имеют значение).
Теперь давайте упростим следующий шаг, связав в оценке:
build_eval(L, Value) :- build_expr(L, Expr), Value is Expr.
Теперь мы сможем найти все уникальные решения, используя setof/3:
6 ?- setof(X, build_eval([10,10,10,10],X), Results).
ERROR: Arithmetic: evaluation error: `zero_divisor'
ERROR: In:
ERROR: [15] _582 is 10/(10* ...)
ERROR: [14] build_eval([10,10|...],_622) at /Users/dlyons/fourtens.pl:11
ERROR: [13] '$bags':findall_loop(_664,user:build_eval(...,_682),_668,[]) at /usr/local/Cellar/swi-prolog/7.6.4/libexec/lib/swipl-7.6.4/boot/bags.pl:97
ERROR: [12] setup_call_catcher_cleanup('$bags':'$new_findall_bag','$bags':findall_loop(_728,...,_732,[]),_710,'$bags':'$destroy_findall_bag') at /usr/local/Cellar/swi-prolog/7.6.4/libexec/lib/swipl-7.6.4/boot/init.pl:443
ERROR: [8] '$bags':setof(_770,user:build_eval(...,_786),_774) at /usr/local/Cellar/swi-prolog/7.6.4/libexec/lib/swipl-7.6.4/boot/bags.pl:240
ERROR: [7] <user>
ERROR:
ERROR: Note: some frames are missing due to last-call optimization.
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.
ERROR: [13] '$bags':findall_loop(_664,user:build_eval(...,_682),_668,[]) aabort
% Execution Aborted
Упс.Деление на ноль ошибок.Нет проблем, давайте поймем это и потерпим неудачу в этих случаях:
9 ?- setof(X, catch(build_eval([10,10,10,10],X), E, fail), Results), writeln(Results).
[-990,-900,-190,-100,-80,-20,-1,-0.1111111111111111,
0,0.01,0.05,0.09090909090909091,0.3333333333333333,1.0,1,
5.0,9.5,9.9,10,10.1,10.5,20.0,20,40,100.0,100,
120,210,300,1010,1100,2000,10000]
Я немного возился с форматированием, но я думаю, что это довольно хорошее решение, но я уже вижу одно отсутствующее решение :(10 + 10) * (10 + 10) = 400.Таким образом, вам придется проявить творческий подход с помощью build_expr/2, чтобы заставить его создавать другие формы дерева.
Редактировать: Добавление остальных решений
Я нашел ответ от @gusbro , который дает возможность перечислять деревья.Я не смог заставить его работать с рекурсивным трюком, который я там делал (возможно, кто-то еще покажет мне очень легкий трюк), но я смог адаптировать его ответ к вашей проблеме, например:
build_tree([I1,I2|Items], Expr) :-
append([L0|LR], [R0|RR], [I1,I2|Items]),
build_tree([L0|LR], Left),
build_tree([R0|RR], Right),
build_expr(Left, Right, Expr).
build_tree([E], E).
Почему я использую [L0|LR] и [R0|RR] вместо LeftList и RightList или что-то подобное?Вот так я превращаю числовые ограничения @ gusbro в ограничения длины списка и гарантирую, что у меня всегда будет хотя бы один элемент в левом и правом списках, поэтому мои рекурсивные вызовы build_tree/2 будут успешными.
Упрощая build_expr/3 сверху вниз до одного оператора, вы можете увидеть, что это генерирует все различные вкусы, которые вы ожидаете:
?- build_tree([10,10,10,10],X).
X = 10+(10+(10+10)) ;
X = 10+(10+10+10) ;
X = 10+10+(10+10) ;
X = 10+(10+10)+10 ;
X = 10+10+10+10 ;
false.
Переключите его обратно, потому что мы все еще используем функцию build_expr/3 изпредыдущий пример.Я несколько упростил оценку, используя этот предикат build_eval/2:
build_eval(L, Value) :-
build_tree(L, Expr), catch(Value is Expr, _, fail).
Вот как выглядит окончательное решение:
?- setof(X, build_eval([10,10,10,10], X), Res), writeln(Res).
[-990,-900,-190,-100,-99,-90,-80,-20,-19,-10,-9.9,-9.5,-9,
-8,-1.1111111111111112,-1,-0.9,-0.1111111111111111,
0,0.01,0.05,0.09090909090909091,0.1111111111111111,
0.2,0.3333333333333333,0.9,0.9090909090909091,1.0,1,
1.1,1.1111111111111112,2,3,5.0,5,8,9,9.5,9.9,10,10.1,10.5,11,
12,19,20.0,20,21,40,80,90,99,100.0,100,101,110,120,190,
200,210,300,400,900,990,1010,1100,2000,10000]
Вау, довольно много альтернатив, 68, если быть точным!