Prolog 中的算术，使用 2 的幂表示数字
Arithmetics in Prolog, represent a number using powers of 2
我有两个数字，我们将它们命名为 N 和 K，我想用 2 的 K 次方来写 N。
例如，如果 N = 9 和 K = 4，则 N 可能是 N = 1 + 2 + 2 + 4 (2^0 + 2^1 + 2^1 + 2^2)。
我的程序应该输出类似 N = [1,2,2,4] 的内容。
我习惯了C++。我在 Prolog 中找不到解决这个问题的方法。任何帮助将不胜感激！
我认为这将是使用 CLP(FD) 的几行，但没有骰子。能不能再简单点？
所以这是完整的解决方案。
不要以为我是一次想出这个的，那里有一些迭代和死胡同。
:- use_module(library(debug)).
% ---
% powersum(+N,+Target,?Solution)
% ---
% Entry point. Relate a list "Solution" of "N" integers to the integer
% "Target", which is the sum of 2^Solution[i].
% This works only in the "functional" direction
% "Compute Solution as powersum(N,Target)"
% or the "verification" direction
% "is Solution a solution of powersum(N,Target)"?
%
% An extension of some interest would be to NOT have a fixed "N".
% Let powersum/2 find appropriate N.
%
% The search is subject to exponential slowdown as the list length
% increases, so one gets bogged down quickly.
% ---
powersum(N,Target,Solution) :-
((integer(N),N>0,integer(Target),Target>=1) -> true ; throw("Bad args!")),
length(RS,N), % create a list RN of N fresh variables
MaxPower is floor(log(Target)/log(2)), % that's the largest power we will find in the solution
propose(RS,MaxPower,Target,0), % generate & test a solution into RS
reverse(RS,Solution), % if we are here, we found something! Reverse RS so that it is increasing
my_write(Solution,String,Value), % prettyprinting
format("~s = ~d\n",[String,Value]).
% ---
% propose(ListForSolution,MaxPowerHere,Target,SumSoFar)
% ---
% This is an integrate "generate-and-test". It is integrated
% to "fail fast" during proposal - we don't want to propose a
% complete solution, then compute the value for that solution
% and find out that we overshot the target. If we overshoot, we
% want to find ozut immediately!
%
% So: Propose a new value for the leftmost position L of the
% solution list. We are allowed to propose any integer for L
% from the sequence [MaxPowerHere,...,0]. "Target" is the target
% value we must not overshoot (indeed, we which must meet
% exactly at the end of recursion). "SumSoFar" is the sum of
% powers "to our left" in the solution list, to which we already
% committed.
propose([L|Ls],MaxPowerHere,Target,SumSoFar) :-
assertion(SumSoFar=<Target),
(SumSoFar=Target -> false ; true), % a slight optimization, no solution if we already reached Target!
propose_value(L,MaxPowerHere), % Generate: L is now (backtrackably) some value from [MaxPowerHere,...,0]
NewSum is (SumSoFar + 2**L),
NewSum =< Target, % Test; if this fails, we backtrack to propose_value/2 and will be back with a next L
NewMaxPowerHere = L, % Test passed; the next power in the sequence should be no larger than the current, i.e. L
propose(Ls,NewMaxPowerHere,Target,NewSum). % Recurse over rest-of-list.
propose([],_,Target,Target). % Terminal test: Only succeed if all values set and the Sum is the Target!
% ---
% propose_value(?X,+Max).
% ---
% Give me a new value X between [Max,0].
% Backtracks over monotonically decreasing integers.
% See the test code for examples.
%
% One could also construct a list of integers [Max,...,0], then
% use "member/2" for backtracking. This would "concretize" the predicate's
% behaviour with an explicit list structure.
%
% "between/3" sadly only generates increasing sequences otherwise one
% could use that. Maybe there is a "between/4" taking a step value somewhere?
% ---
propose_value(X,Max) :-
assertion((integer(Max),Max>=0)),
Max=X.
propose_value(X,Max) :-
assertion((integer(Max),Max>=0)),
Max>0, succ(NewMax,Max),
propose_value(X,NewMax).
% ---
% I like some nice output, so generate a string representing the solution.
% Also, recompute the value to make doubly sure!
% ---
my_write([L|Ls],String,Value) :-
my_write(Ls,StringOnTheRight,ValueOnTheRight),
Value is ValueOnTheRight + 2**L,
with_output_to(string(String),format("2^~d + ~s",[L,StringOnTheRight])).
my_write([L],String,Value) :-
with_output_to(string(String),format("2^~d",[L])),
Value is 2**L.
:- begin_tests(powersum).
% powersum(N,Target,Solution)
test(pv1) :- bagof(X,propose_value(X,3),Bag), Bag = [3,2,1,0].
test(pv2) :- bagof(X,propose_value(X,2),Bag), Bag = [2,1,0].
test(pv2) :- bagof(X,propose_value(X,1),Bag), Bag = [1,0].
test(pv3) :- bagof(X,propose_value(X,0),Bag), Bag = [0].
test(one) :- bagof(S,powersum(1,1,S),Bag), Bag = [[0]].
test(two) :- bagof(S,powersum(3,10,S),Bag), Bag = [[0,0,3],[1,2,2]].
test(three) :- bagof(S,powersum(3,145,S),Bag), Bag = [[0,4,7]].
test(four,fail) :- powersum(3,8457894,_).
test(five) :- bagof(S,powersum(9,8457894,S), Bag), Bag = [[1, 2, 5, 7, 9, 10, 11, 16, 23]]. %% VERY SLOW
:- end_tests(powersum).
rt :- run_tests(powersum).
运行 测试2分钟由于最后一行单元测试...
?- time(rt).
% PL-Unit: powersum ....2^0 = 1
.2^0 + 2^0 + 2^3 = 10
2^1 + 2^2 + 2^2 = 10
.2^0 + 2^4 + 2^7 = 145
..2^1 + 2^2 + 2^5 + 2^7 + 2^9 + 2^10 + 2^11 + 2^16 + 2^23 = 8457894
. done
% All 9 tests passed
% 455,205,628 inferences, 114.614 CPU in 115.470 seconds (99% CPU, 3971641 Lips)
true.
这是一个使用CLP(FD)的方案。通常，在 Prolog 中的整数域中进行推理时，CLP(FD) 是一个不错的选择。这个特定问题的想法是递归思考（就像在许多 Prolog 问题中一样）并使用 "bifurcation" 方法。
正如 David 在他的回答中所说，解决此类问题的方法不会在第一次尝试时就出现。有初步的概念、试验实施、测试、观察和修订，这些都是为了提出问题的解决方案。即使是这个也需要更多的工作。 :)
:- use_module(library(clpfd)).
% Predicate that succeeds for power of 2
power_of_2(1).
power_of_2(N) :-
N #> 1,
NH #= N // 2,
N #= NH * 2,
power_of_2(NH).
% Predicate that succeeds for a list that is monotonically ascending
ascending([_]).
ascending([X1,X2|Xs]) :-
X1 #=< X2,
ascending([X2|Xs]).
% Predicate that succeeds if Partition is a K-part partition of N
% where the parts are powers of 2
binary_partition(N, K, Partition) :-
binary_partition_(N, K, Partition),
ascending(Partition). % Only allow ascending lists as solutions
binary_partition_(N, 1, [N]) :- % base case
power_of_2(N).
binary_partition_(N, K, P) :-
N #> 1, % constraints on N, K
K #> 1,
length(P, K), % constraint on P
append(LL, LR, P), % conditions on left/right bifurcation
NL #> 0,
NR #> 0,
KL #> 0,
KR #> 0,
NL #=< NR, % don't count symmetrical cases
KL #=< KR,
N #= NL + NR,
K #= KL + KR,
binary_partition_(NL, KL, LL),
binary_partition_(NR, KR, LR).
这将提供正确的结果，但也会生成冗余的解决方案：
2 ?- binary_partition(9,4,L).
L = [1, 2, 2, 4] ;
L = [1, 2, 2, 4] ;
false.
作为练习，您可以弄清楚如何修改它，使其只生成唯一的解决方案。 :)
编辑： 根据 repeat 的一些建议性评论，这里是一个完整、高效的 CLP(FD) 解决方案：
powersum2_(N, Target, Exponents, Solution) :-
length(Exponents, N),
MaxExponent is floor(log(Target) / log(2)),
Exponents ins 0..MaxExponent,
chain(Exponents, #>=),
maplist(exponent_power, Exponents, Solution),
sum(Solution, #=, Target).
exponent_power(Exponent, Power) :-
Power #= 2^Exponent.
powersum2(N, Target, Solution) :-
powersum2_(N, Target, Exponents, Solution),
labeling([], Exponents).
按 #>= 排序指数通过排除冗余排列减少了搜索 space。但它也与标记顺序有关（使用 [] 策略）。
核心关系powersum2_/4 post对数的约束：
?- powersum2_(5, 31, Exponents, Solution).
Exponents = [_954, _960, _966, _972, _978],
Solution = [_984, _990, _996, _1002, _1008],
_954 in 0..4,
_954#>=_960,
2^_954#=_984,
_960 in 0..4,
_960#>=_966,
2^_960#=_990,
_966 in 0..4,
_966#>=_972,
2^_966#=_996,
_972 in 0..4,
_972#>=_978,
2^_972#=_1002,
_978 in 0..4,
2^_978#=_1008,
_1008 in 1..16,
_984+_990+_996+_1002+_1008#=31,
_984 in 1..16,
_990 in 1..16,
_996 in 1..16,
_1002 in 1..16.
然后标记搜索实际解决方案：
?- powersum2(5, 31, Solution).
Solution = [16, 8, 4, 2, 1] ;
false.
到目前为止，此解决方案比其他答案更有效：
?- time(powersum2(9, 8457894, Solution)).
% 6,957,285 inferences, 0.589 CPU in 0.603 seconds (98% CPU, 11812656 Lips)
Solution = [8388608, 65536, 2048, 1024, 512, 128, 32, 4, 2].
原文如下
这是另一个 CLP(FD) 解决方案。这个想法是将 "power of two" 表示为 "real" 约束，即不像 lurker 的 power_of_2/1 那样作为枚举数字的谓词。有助于表达的 actual 约束不是真正的 "power of two"，而是 "power of two less than or equal to a known bound".
所以这里有一些笨拙的代码来计算 2 的幂列表直到一个限制：
powers_of_two_bound(PowersOfTwo, UpperBound) :-
powers_of_two_bound(1, PowersOfTwo, UpperBound).
powers_of_two_bound(Power, [Power], UpperBound) :-
Power =< UpperBound,
Power * 2 > UpperBound.
powers_of_two_bound(Power, [Power | PowersOfTwo], UpperBound) :-
Power =< UpperBound,
NextPower is Power * 2,
powers_of_two_bound(NextPower, PowersOfTwo, UpperBound).
?- powers_of_two_bound(Powers, 1023).
Powers = [1, 2, 4, 8, 16, 32, 64, 128, 256|...] ;
false.
...然后根据此计算约束项...
power_of_two_constraint(UpperBound, Variable, Constraint) :-
powers_of_two_bound(PowersOfTwo, UpperBound),
maplist(fd_equals(Variable), PowersOfTwo, PowerOfTwoConstraints),
constraints_operator_combined(PowerOfTwoConstraints, #\/, Constraint).
fd_equals(Variable, Value, Variable #= Value).
constraints_operator_combined([Constraint], _Operator, Constraint).
constraints_operator_combined([C | Cs], Operator, Constraint) :-
Constraint =.. [Operator, C, NextConstraint],
constraints_operator_combined(Cs, Operator, NextConstraint).
?- power_of_two_constraint(1023, X, Constraint).
Constraint = (X#=1#\/(X#=2#\/(X#=4#\/(X#=8#\/(X#=16#\/(X#=32#\/(X#=64#\/(X#=128#\/(... #= ... #\/ ... #= ...))))))))) ;
false.
... 然后 post 该约束：
power_of_two(Target, Variable) :-
power_of_two_constraint(Target, Variable, Constraint),
call(Constraint).
?- power_of_two(1023, X).
X in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512 ;
false.
（看到以这种语法打印的内容表明我可以简化计算约束项的代码...）
然后核心关系是：
powersum_(N, Target, Solution) :-
length(Solution, N),
maplist(power_of_two(Target), Solution),
list_monotonic(Solution, #=<),
sum(Solution, #=, Target).
list_monotonic([], _Operation).
list_monotonic([_X], _Operation).
list_monotonic([X, Y | Xs], Operation) :-
call(Operation, X, Y),
list_monotonic([Y | Xs], Operation).
我们可以 运行 不加标签：
?- powersum_(9, 1023, S).
S = [_9158, _9164, _9170, _9176, _9182, _9188, _9194, _9200, _9206],
_9158 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9158+_9164+_9170+_9176+_9182+_9188+_9194+_9200+_9206#=1023,
_9164#>=_9158,
_9164 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9170#>=_9164,
_9170 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9176#>=_9170,
_9176 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9182#>=_9176,
_9182 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9188#>=_9182,
_9188 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9194#>=_9188,
_9194 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9200#>=_9194,
_9200 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9206#>=_9200,
_9206 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512 ;
false.
而且我们标记的时候有点快：
?- time(( powersum_(8, 255, S), labeling([], S) )), format('S = ~w~n', [S]), false.
% 561,982 inferences, 0.055 CPU in 0.055 seconds (100% CPU, 10238377 Lips)
S = [1,2,4,8,16,32,64,128]
% 1,091,295 inferences, 0.080 CPU in 0.081 seconds (100% CPU, 13557999 Lips)
false.
将此与潜伏者的方法进行对比，潜伏者的方法甚至需要更长的时间才能找到第一个解决方案：
?- time(binary_partition(255, 8, S)), format('S = ~w~n', [S]), false.
% 402,226,596 inferences, 33.117 CPU in 33.118 seconds (100% CPU, 12145562 Lips)
S = [1,2,4,8,16,32,64,128]
% 1,569,157 inferences, 0.130 CPU in 0.130 seconds (100% CPU, 12035050 Lips)
S = [1,2,4,8,16,32,64,128]
% 14,820,953 inferences, 1.216 CPU in 1.216 seconds (100% CPU, 12190530 Lips)
S = [1,2,4,8,16,32,64,128]
% 159,089,361 inferences, 13.163 CPU in 13.163 seconds (100% CPU, 12086469 Lips)
S = [1,2,4,8,16,32,64,128]
% 1,569,155 inferences, 0.134 CPU in 0.134 seconds (100% CPU, 11730834 Lips)
S = [1,2,4,8,16,32,64,128]
% 56,335,514 inferences, 4.684 CPU in 4.684 seconds (100% CPU, 12027871 Lips)
S = [1,2,4,8,16,32,64,128]
^CAction (h for help) ? abort
% 1,266,275,462 inferences, 107.019 CPU in 107.839 seconds (99% CPU, 11832284 Lips)
% Execution Aborted % got bored of waiting
但是，此解决方案比 David Tonhofer 的解决方案慢：
?- time(( powersum_(9, 8457894, S), labeling([], S) )), format('S = ~w~n', [S]), false.
% 827,367,193 inferences, 58.396 CPU in 58.398 seconds (100% CPU, 14168325 Lips)
S = [2,4,32,128,512,1024,2048,65536,8388608]
% 1,715,107,811 inferences, 124.528 CPU in 124.532 seconds (100% CPU, 13772907 Lips)
false.
对比：
?- time(bagof(S,powersum(9,8457894,S), Bag)).
2^1 + 2^2 + 2^5 + 2^7 + 2^9 + 2^10 + 2^11 + 2^16 + 2^23 = 8457894
% 386,778,067 inferences, 37.705 CPU in 37.706 seconds (100% CPU, 10258003 Lips)
Bag = [[1, 2, 5, 7, 9, 10, 11, 16|...]].
我的限制可能还有改进的余地，或者可能有一些神奇的标签策略可以改进搜索。
编辑：哈！从最大元素到最小元素的标签会显着改变性能：
?- time(( powersum_(9, 8457894, S), reverse(S, Rev), labeling([], Rev) )), format('S = ~w~n', [S]), false.
% 5,320,573 inferences, 0.367 CPU in 0.367 seconds (100% CPU, 14495124 Lips)
S = [2,4,32,128,512,1024,2048,65536,8388608]
% 67 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 2618313 Lips)
false.
所以这现在大约是 David Tonhofer 版本的 100 倍。我对此很满意:-)
my_power_of_two_bound(U,P):-
U #>= 2^P,
P #=< U,
P #>=0.
power2(X,Y):-
Y #= 2^X.
查询：
?- N=9,K=4,
length(_List,K),
maplist(my_power_of_two_bound(N),_List),
maplist(power2,_List,Answer),
chain(Answer, #=<),
sum(Answer, #=, N),
label(Answer).
然后：
Answer = [1, 2, 2, 4],
K = 4,
N = 9
我有两个数字，我们将它们命名为 N 和 K，我想用 2 的 K 次方来写 N。
例如，如果 N = 9 和 K = 4，则 N 可能是 N = 1 + 2 + 2 + 4 (2^0 + 2^1 + 2^1 + 2^2)。
我的程序应该输出类似 N = [1,2,2,4] 的内容。
我习惯了C++。我在 Prolog 中找不到解决这个问题的方法。任何帮助将不胜感激！
我认为这将是使用 CLP(FD) 的几行，但没有骰子。能不能再简单点？
所以这是完整的解决方案。
不要以为我是一次想出这个的，那里有一些迭代和死胡同。
:- use_module(library(debug)).
% ---
% powersum(+N,+Target,?Solution)
% ---
% Entry point. Relate a list "Solution" of "N" integers to the integer
% "Target", which is the sum of 2^Solution[i].
% This works only in the "functional" direction
% "Compute Solution as powersum(N,Target)"
% or the "verification" direction
% "is Solution a solution of powersum(N,Target)"?
%
% An extension of some interest would be to NOT have a fixed "N".
% Let powersum/2 find appropriate N.
%
% The search is subject to exponential slowdown as the list length
% increases, so one gets bogged down quickly.
% ---
powersum(N,Target,Solution) :-
((integer(N),N>0,integer(Target),Target>=1) -> true ; throw("Bad args!")),
length(RS,N), % create a list RN of N fresh variables
MaxPower is floor(log(Target)/log(2)), % that's the largest power we will find in the solution
propose(RS,MaxPower,Target,0), % generate & test a solution into RS
reverse(RS,Solution), % if we are here, we found something! Reverse RS so that it is increasing
my_write(Solution,String,Value), % prettyprinting
format("~s = ~d\n",[String,Value]).
% ---
% propose(ListForSolution,MaxPowerHere,Target,SumSoFar)
% ---
% This is an integrate "generate-and-test". It is integrated
% to "fail fast" during proposal - we don't want to propose a
% complete solution, then compute the value for that solution
% and find out that we overshot the target. If we overshoot, we
% want to find ozut immediately!
%
% So: Propose a new value for the leftmost position L of the
% solution list. We are allowed to propose any integer for L
% from the sequence [MaxPowerHere,...,0]. "Target" is the target
% value we must not overshoot (indeed, we which must meet
% exactly at the end of recursion). "SumSoFar" is the sum of
% powers "to our left" in the solution list, to which we already
% committed.
propose([L|Ls],MaxPowerHere,Target,SumSoFar) :-
assertion(SumSoFar=<Target),
(SumSoFar=Target -> false ; true), % a slight optimization, no solution if we already reached Target!
propose_value(L,MaxPowerHere), % Generate: L is now (backtrackably) some value from [MaxPowerHere,...,0]
NewSum is (SumSoFar + 2**L),
NewSum =< Target, % Test; if this fails, we backtrack to propose_value/2 and will be back with a next L
NewMaxPowerHere = L, % Test passed; the next power in the sequence should be no larger than the current, i.e. L
propose(Ls,NewMaxPowerHere,Target,NewSum). % Recurse over rest-of-list.
propose([],_,Target,Target). % Terminal test: Only succeed if all values set and the Sum is the Target!
% ---
% propose_value(?X,+Max).
% ---
% Give me a new value X between [Max,0].
% Backtracks over monotonically decreasing integers.
% See the test code for examples.
%
% One could also construct a list of integers [Max,...,0], then
% use "member/2" for backtracking. This would "concretize" the predicate's
% behaviour with an explicit list structure.
%
% "between/3" sadly only generates increasing sequences otherwise one
% could use that. Maybe there is a "between/4" taking a step value somewhere?
% ---
propose_value(X,Max) :-
assertion((integer(Max),Max>=0)),
Max=X.
propose_value(X,Max) :-
assertion((integer(Max),Max>=0)),
Max>0, succ(NewMax,Max),
propose_value(X,NewMax).
% ---
% I like some nice output, so generate a string representing the solution.
% Also, recompute the value to make doubly sure!
% ---
my_write([L|Ls],String,Value) :-
my_write(Ls,StringOnTheRight,ValueOnTheRight),
Value is ValueOnTheRight + 2**L,
with_output_to(string(String),format("2^~d + ~s",[L,StringOnTheRight])).
my_write([L],String,Value) :-
with_output_to(string(String),format("2^~d",[L])),
Value is 2**L.
:- begin_tests(powersum).
% powersum(N,Target,Solution)
test(pv1) :- bagof(X,propose_value(X,3),Bag), Bag = [3,2,1,0].
test(pv2) :- bagof(X,propose_value(X,2),Bag), Bag = [2,1,0].
test(pv2) :- bagof(X,propose_value(X,1),Bag), Bag = [1,0].
test(pv3) :- bagof(X,propose_value(X,0),Bag), Bag = [0].
test(one) :- bagof(S,powersum(1,1,S),Bag), Bag = [[0]].
test(two) :- bagof(S,powersum(3,10,S),Bag), Bag = [[0,0,3],[1,2,2]].
test(three) :- bagof(S,powersum(3,145,S),Bag), Bag = [[0,4,7]].
test(four,fail) :- powersum(3,8457894,_).
test(five) :- bagof(S,powersum(9,8457894,S), Bag), Bag = [[1, 2, 5, 7, 9, 10, 11, 16, 23]]. %% VERY SLOW
:- end_tests(powersum).
rt :- run_tests(powersum).
运行 测试2分钟由于最后一行单元测试...
?- time(rt).
% PL-Unit: powersum ....2^0 = 1
.2^0 + 2^0 + 2^3 = 10
2^1 + 2^2 + 2^2 = 10
.2^0 + 2^4 + 2^7 = 145
..2^1 + 2^2 + 2^5 + 2^7 + 2^9 + 2^10 + 2^11 + 2^16 + 2^23 = 8457894
. done
% All 9 tests passed
% 455,205,628 inferences, 114.614 CPU in 115.470 seconds (99% CPU, 3971641 Lips)
true.
这是一个使用CLP(FD)的方案。通常，在 Prolog 中的整数域中进行推理时，CLP(FD) 是一个不错的选择。这个特定问题的想法是递归思考（就像在许多 Prolog 问题中一样）并使用 "bifurcation" 方法。
正如 David 在他的回答中所说，解决此类问题的方法不会在第一次尝试时就出现。有初步的概念、试验实施、测试、观察和修订，这些都是为了提出问题的解决方案。即使是这个也需要更多的工作。 :)
:- use_module(library(clpfd)).
% Predicate that succeeds for power of 2
power_of_2(1).
power_of_2(N) :-
N #> 1,
NH #= N // 2,
N #= NH * 2,
power_of_2(NH).
% Predicate that succeeds for a list that is monotonically ascending
ascending([_]).
ascending([X1,X2|Xs]) :-
X1 #=< X2,
ascending([X2|Xs]).
% Predicate that succeeds if Partition is a K-part partition of N
% where the parts are powers of 2
binary_partition(N, K, Partition) :-
binary_partition_(N, K, Partition),
ascending(Partition). % Only allow ascending lists as solutions
binary_partition_(N, 1, [N]) :- % base case
power_of_2(N).
binary_partition_(N, K, P) :-
N #> 1, % constraints on N, K
K #> 1,
length(P, K), % constraint on P
append(LL, LR, P), % conditions on left/right bifurcation
NL #> 0,
NR #> 0,
KL #> 0,
KR #> 0,
NL #=< NR, % don't count symmetrical cases
KL #=< KR,
N #= NL + NR,
K #= KL + KR,
binary_partition_(NL, KL, LL),
binary_partition_(NR, KR, LR).
这将提供正确的结果，但也会生成冗余的解决方案：
2 ?- binary_partition(9,4,L).
L = [1, 2, 2, 4] ;
L = [1, 2, 2, 4] ;
false.
作为练习，您可以弄清楚如何修改它，使其只生成唯一的解决方案。 :)
编辑： 根据 repeat 的一些建议性评论，这里是一个完整、高效的 CLP(FD) 解决方案：
powersum2_(N, Target, Exponents, Solution) :-
length(Exponents, N),
MaxExponent is floor(log(Target) / log(2)),
Exponents ins 0..MaxExponent,
chain(Exponents, #>=),
maplist(exponent_power, Exponents, Solution),
sum(Solution, #=, Target).
exponent_power(Exponent, Power) :-
Power #= 2^Exponent.
powersum2(N, Target, Solution) :-
powersum2_(N, Target, Exponents, Solution),
labeling([], Exponents).
按 #>= 排序指数通过排除冗余排列减少了搜索 space。但它也与标记顺序有关（使用 [] 策略）。
核心关系powersum2_/4 post对数的约束：
?- powersum2_(5, 31, Exponents, Solution).
Exponents = [_954, _960, _966, _972, _978],
Solution = [_984, _990, _996, _1002, _1008],
_954 in 0..4,
_954#>=_960,
2^_954#=_984,
_960 in 0..4,
_960#>=_966,
2^_960#=_990,
_966 in 0..4,
_966#>=_972,
2^_966#=_996,
_972 in 0..4,
_972#>=_978,
2^_972#=_1002,
_978 in 0..4,
2^_978#=_1008,
_1008 in 1..16,
_984+_990+_996+_1002+_1008#=31,
_984 in 1..16,
_990 in 1..16,
_996 in 1..16,
_1002 in 1..16.
然后标记搜索实际解决方案：
?- powersum2(5, 31, Solution).
Solution = [16, 8, 4, 2, 1] ;
false.
到目前为止，此解决方案比其他答案更有效：
?- time(powersum2(9, 8457894, Solution)).
% 6,957,285 inferences, 0.589 CPU in 0.603 seconds (98% CPU, 11812656 Lips)
Solution = [8388608, 65536, 2048, 1024, 512, 128, 32, 4, 2].
原文如下
这是另一个 CLP(FD) 解决方案。这个想法是将 "power of two" 表示为 "real" 约束，即不像 lurker 的 power_of_2/1 那样作为枚举数字的谓词。有助于表达的 actual 约束不是真正的 "power of two"，而是 "power of two less than or equal to a known bound".
所以这里有一些笨拙的代码来计算 2 的幂列表直到一个限制：
powers_of_two_bound(PowersOfTwo, UpperBound) :-
powers_of_two_bound(1, PowersOfTwo, UpperBound).
powers_of_two_bound(Power, [Power], UpperBound) :-
Power =< UpperBound,
Power * 2 > UpperBound.
powers_of_two_bound(Power, [Power | PowersOfTwo], UpperBound) :-
Power =< UpperBound,
NextPower is Power * 2,
powers_of_two_bound(NextPower, PowersOfTwo, UpperBound).
?- powers_of_two_bound(Powers, 1023).
Powers = [1, 2, 4, 8, 16, 32, 64, 128, 256|...] ;
false.
...然后根据此计算约束项...
power_of_two_constraint(UpperBound, Variable, Constraint) :-
powers_of_two_bound(PowersOfTwo, UpperBound),
maplist(fd_equals(Variable), PowersOfTwo, PowerOfTwoConstraints),
constraints_operator_combined(PowerOfTwoConstraints, #\/, Constraint).
fd_equals(Variable, Value, Variable #= Value).
constraints_operator_combined([Constraint], _Operator, Constraint).
constraints_operator_combined([C | Cs], Operator, Constraint) :-
Constraint =.. [Operator, C, NextConstraint],
constraints_operator_combined(Cs, Operator, NextConstraint).
?- power_of_two_constraint(1023, X, Constraint).
Constraint = (X#=1#\/(X#=2#\/(X#=4#\/(X#=8#\/(X#=16#\/(X#=32#\/(X#=64#\/(X#=128#\/(... #= ... #\/ ... #= ...))))))))) ;
false.
... 然后 post 该约束：
power_of_two(Target, Variable) :-
power_of_two_constraint(Target, Variable, Constraint),
call(Constraint).
?- power_of_two(1023, X).
X in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512 ;
false.
（看到以这种语法打印的内容表明我可以简化计算约束项的代码...）
然后核心关系是：
powersum_(N, Target, Solution) :-
length(Solution, N),
maplist(power_of_two(Target), Solution),
list_monotonic(Solution, #=<),
sum(Solution, #=, Target).
list_monotonic([], _Operation).
list_monotonic([_X], _Operation).
list_monotonic([X, Y | Xs], Operation) :-
call(Operation, X, Y),
list_monotonic([Y | Xs], Operation).
我们可以 运行 不加标签：
?- powersum_(9, 1023, S).
S = [_9158, _9164, _9170, _9176, _9182, _9188, _9194, _9200, _9206],
_9158 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9158+_9164+_9170+_9176+_9182+_9188+_9194+_9200+_9206#=1023,
_9164#>=_9158,
_9164 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9170#>=_9164,
_9170 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9176#>=_9170,
_9176 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9182#>=_9176,
_9182 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9188#>=_9182,
_9188 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9194#>=_9188,
_9194 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9200#>=_9194,
_9200 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512,
_9206#>=_9200,
_9206 in ... .. ... \/ 4\/8\/16\/32\/64\/128\/256\/512 ;
false.
而且我们标记的时候有点快：
?- time(( powersum_(8, 255, S), labeling([], S) )), format('S = ~w~n', [S]), false.
% 561,982 inferences, 0.055 CPU in 0.055 seconds (100% CPU, 10238377 Lips)
S = [1,2,4,8,16,32,64,128]
% 1,091,295 inferences, 0.080 CPU in 0.081 seconds (100% CPU, 13557999 Lips)
false.
将此与潜伏者的方法进行对比，潜伏者的方法甚至需要更长的时间才能找到第一个解决方案：
?- time(binary_partition(255, 8, S)), format('S = ~w~n', [S]), false.
% 402,226,596 inferences, 33.117 CPU in 33.118 seconds (100% CPU, 12145562 Lips)
S = [1,2,4,8,16,32,64,128]
% 1,569,157 inferences, 0.130 CPU in 0.130 seconds (100% CPU, 12035050 Lips)
S = [1,2,4,8,16,32,64,128]
% 14,820,953 inferences, 1.216 CPU in 1.216 seconds (100% CPU, 12190530 Lips)
S = [1,2,4,8,16,32,64,128]
% 159,089,361 inferences, 13.163 CPU in 13.163 seconds (100% CPU, 12086469 Lips)
S = [1,2,4,8,16,32,64,128]
% 1,569,155 inferences, 0.134 CPU in 0.134 seconds (100% CPU, 11730834 Lips)
S = [1,2,4,8,16,32,64,128]
% 56,335,514 inferences, 4.684 CPU in 4.684 seconds (100% CPU, 12027871 Lips)
S = [1,2,4,8,16,32,64,128]
^CAction (h for help) ? abort
% 1,266,275,462 inferences, 107.019 CPU in 107.839 seconds (99% CPU, 11832284 Lips)
% Execution Aborted % got bored of waiting
但是，此解决方案比 David Tonhofer 的解决方案慢：
?- time(( powersum_(9, 8457894, S), labeling([], S) )), format('S = ~w~n', [S]), false.
% 827,367,193 inferences, 58.396 CPU in 58.398 seconds (100% CPU, 14168325 Lips)
S = [2,4,32,128,512,1024,2048,65536,8388608]
% 1,715,107,811 inferences, 124.528 CPU in 124.532 seconds (100% CPU, 13772907 Lips)
false.
对比：
?- time(bagof(S,powersum(9,8457894,S), Bag)).
2^1 + 2^2 + 2^5 + 2^7 + 2^9 + 2^10 + 2^11 + 2^16 + 2^23 = 8457894
% 386,778,067 inferences, 37.705 CPU in 37.706 seconds (100% CPU, 10258003 Lips)
Bag = [[1, 2, 5, 7, 9, 10, 11, 16|...]].
我的限制可能还有改进的余地，或者可能有一些神奇的标签策略可以改进搜索。
编辑：哈！从最大元素到最小元素的标签会显着改变性能：
?- time(( powersum_(9, 8457894, S), reverse(S, Rev), labeling([], Rev) )), format('S = ~w~n', [S]), false.
% 5,320,573 inferences, 0.367 CPU in 0.367 seconds (100% CPU, 14495124 Lips)
S = [2,4,32,128,512,1024,2048,65536,8388608]
% 67 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 2618313 Lips)
false.
所以这现在大约是 David Tonhofer 版本的 100 倍。我对此很满意:-)
my_power_of_two_bound(U,P):-
U #>= 2^P,
P #=< U,
P #>=0.
power2(X,Y):-
Y #= 2^X.
查询：
?- N=9,K=4,
length(_List,K),
maplist(my_power_of_two_bound(N),_List),
maplist(power2,_List,Answer),
chain(Answer, #=<),
sum(Answer, #=, N),
label(Answer).
然后：
Answer = [1, 2, 2, 4],
K = 4,
N = 9