/* 

  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.