/*
Four number problem in Picat.
From
http://stackoverflow.com/questions/17720465/given-4-numbers-of-array-of-1-to-10-elements-find-3-numbers-whose-sum-can-gener
"Given 4 numbers of array of 1 to 10 elements.
Find 3 numbers whose sum can generate all the four numbers?"
"""
I am given an array containing a list of 4 random numbers (1 to 10 inclusive).
I am supposed to generate a list of 3 numbers (1 to 10 inclusive) so that I can
generate all the 4 numbers of the initial list by adding the 3 numbers of
the generated list.
Someone Please provide an algorithm for doing this.
"""
For the problem instance mentioned in a comment [1,3,7,8], there are 5 solutions:
r: [1, 3, 7, 8]
x: [1, 3, 4]
----------
r: [1, 3, 7, 8]
x: [1, 2, 5]
----------
r: [1, 3, 7, 8]
x: [1, 2, 6]
----------
r: [1, 3, 7, 8]
x: [1, 2, 7]
----------
r: [1, 3, 7, 8]
x: [1, 3, 7]
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
% import util.
import cp.
main => go.
go =>
R = [1,3,7,8], % random number
N = 3,
four_numbers(R,N,All),
foreach(X in All)
writeln(X)
end,
nl.
% generate random numbers
go2 =>
M = 4,
N = 3,
rand_perm(1..10, M, R1),
R = R1.sort(),
writeln(r=R),
nl,
four_numbers(R,N,All),
foreach(X in All)
writeln(x=X)
end,
nl.
four_numbers(R,N, All) =>
M = R.length,
X = new_list(N),
X :: 1..10,
% coefficient matrix
Tmp = new_array(M,N),
Tmp :: 0..1,
foreach(I in 1..M)
sum([Tmp[I,J]*X[J] : J in 1..N]) #= R[I]
end,
increasing(X),
All=solve_all([split], X).
increasing(List) =>
foreach(I in 2..List.length) List[I-1] #=< List[I] end.
rand_perm(L) = L, L.length == 1 => true.
rand_perm(L) = L => rand_perm(L, L.length, _Perm).
rand_perm(_,0,R) ?=> R = [].
rand_perm(Xs,N,R) ?=>
R = [X|Zs],
N > 0,
L = length(Xs),
I = 1+random2() mod L,
remove_at(X,Xs,I,Ys),
N1 = N - 1,
rand_perm(Ys,N1,Zs).
remove_at(X,L,1,R) => L=[X|Xs], R=Xs.
remove_at(X,L,K,R) => L=[Y|Xs], R=[Y|Ys], K #> 1, K1 #= K - 1, remove_at(X,Xs,K1,Ys).
% random selection _with_ replacement
rnd_select2(L,N,R) =>
R1 = [],
Len = L.length,
foreach(_I in 1..N)
E = L[1+random2() mod Len],
R1 := R1 ++ [E]
end,
R = R1.