Summing to a target value

[Imp1]

I have a problem that I can summarise as:

I have the numbers 1-10 in a variable and have to keep the numbers that will sum to 20 (e.g. 3, 8 & 9)

The only way I can think of doing this is transposing and then with a lot of do loops and a do until. Unfortunately when I put the problem into practice there could be over 100 numbers summing to the target number.

Has anyone got any ideas?

[PhilC]

I think some computer science teachers might like to use this problem to teach the subject of recursion.  As far as SAS goes, you can learn PROC FCMP which will let you do recursion.  But I haven't done this in SAS myself.  

SAS Help Center: Recursion

[PhilC]

... you would need to access an Hash Object too.  Ok I'm intrigued, now.   

[PhilC]

I did not use recursion, only one do loop surprisingly.  I think it would be handled better with recursion in C, because of array pointers, based on my own experience.  I do this kind of thing, on paper by hand, so much when I play my favorite logic puzzles.  It was fun and frustrating too. 

(Thanks for all the other submissions.)

data want (keep=a01-a10);
  array a[0:10] a00-a10;
  array sum[0:10] s00-s10;
  x=1;
  a[0]=0;
  a[x]=a[x-1];
  sum[0]=0;
  goal=20;
  do while (a[x]<10 and x>0); a[x]+1;
    Sum[x]=sum[x-1]+a[x];
    Just_right=sum[x]=goal;
    If Just_right 
      then output;
    GoToNext = sum[x]>=goal or x>9 or a[x]>9;
    Promote_up= not GoToNext;
    If GoToNext then do;
      a[x]=.;
      sum[x]=.;
      x=x-1;/*demote index*/
      end;
    if Promote_up then do; /*Promote up index*/
      x=x+1;     
      a[x]=a[x-1];
    end;
  end;
run;

[Shmuel]

Suppose your variable is:  data_in = "1 2 3 4 5 6 7 8 9 10";

1) assign each number to a different variable: v1-v10 using scan() function.

     now you have 10 variables with value > 0.

2) choose randomly any integer between 1 and 10; (with ranuni() function or other )

     - subtract the number from 20 and keep the difference in a variable diff. 

     - assign 0 to v(number)

     - save the v(number) in a list if its value is not 0.

3) if diff >10 repeat step 2

    else, if diff <=10 that is the last number to save.

Try to code it and post your code when you have any issue.

[Astounding]

Must you always choose 3 of the numbers?

If there is more than one combination that sums to 20 do you want all possible combinations?

In your example, 8 + 9 + 1 + 2 = 20.  Also 5 + 3 + 9 + 1 + 2 = 20.  So what result do you want?  1, 2, 3, 5, 8, 9?

[PGStats]

Use the ALLCOMB function to check all combinations.

/* Fake data */
data have;
call streaminit(865764579);
do case = 1 to 30;
    nbNums = rand("integer", 1, 8);
    do i = 1 to nbNums;
        num = rand("integer", 1, 10);
        output;
        end;
    end;
keep case num;
run;

data want;
array c{*} c1-c8;
do nbNums = 1 by 1 until(last.case);
    set have; by case;
    c{nbNums} = num;
    end;
k = 3;
if nbNums >= k then do;
    ncomb = comb(nbNums, k);
    do j = 1 to ncomb+1;
        select (nbNums);
            when(3) rc = 1;
            when(4) do; rc = allcomb(j, k, of c1-c4); end;
            when(5) do; rc = allcomb(j, k, of c1-c5); end;
            when(6) do; rc = allcomb(j, k, of c1-c6); end;
            when(7) do; rc = allcomb(j, k, of c1-c7); end;
            when(8) do; rc = allcomb(j, k, of c1-c8); end;
            otherwise rc = -1;
            end;
        if rc >= 0 then if sum(c1,c2,c3) = 20 then do;
            output;
            /* leave */; /* If you only want one combination */
            end;
        end;
    end;
keep case c1 c2 c3;
run;

proc print noobs data=want; var case c1-c3; run;

[Ksharp]

the best choice is SAS/OR if you have it . post your questions at OR forum

and calling @RobPratt 

[RobPratt]

You can use the constraint programming solver in PROC OPTMODEL:

proc optmodel;
   num n = 10;
   num target = 20;

   /* X[j] = 1 if j is selected; 0 otherwise */
   var X {1..n} binary;

   /* selected numbers must sum to target */
   con Partition:
      sum {j in 1..n} j * X[j] = target;

   solve with clp / findallsolns;
   for {s in 1.._NSOL_} do;
      for {j in 1..n: X[j].sol[s] > 0.5} put j @;
      put;
   end;
quit;

The resulting partitions are:

5 7 8
5 6 9
4 7 9
4 6 10
3 8 9
3 7 10
3 4 6 7
3 4 5 8
2 8 10
2 5 6 7
2 4 6 8
2 4 5 9
2 3 7 8
2 3 6 9
2 3 5 10
2 3 4 5 6
1 9 10
1 5 6 8
1 4 7 8
1 4 6 9
1 4 5 10
1 3 7 9
1 3 6 10
1 3 4 5 7
1 2 8 9
1 2 7 10
1 2 4 6 7
1 2 4 5 8
1 2 3 6 8
1 2 3 5 9
1 2 3 4 10

If you want to restrict to exactly three summands, you can add this constraint:

   /* select three numbers */
   con Cardinality:
      sum {j in 1..n} X[j] = 3;   

5 7 8
5 6 9
4 7 9
4 6 10
3 8 9
3 7 10
2 8 10
1 9 10

If you want to allow the same number to appear more than once, you can change the VAR statement:

   var X {1..n} >= 0 integer;

And then also change the FOR loop:

   for {s in 1.._NSOL_} do;
      for {j in 1..n, 1..round(X[j].sol[s])} put j @;
      put;
   end;

5 5 10
4 6 10
5 6 9
1 9 10
2 9 9
6 6 8
2 8 10
3 8 9
4 8 8
3 7 10
4 7 9
5 7 8
6 7 7

If you want the order to matter (to distinguish 3 8 9 from 8 3 9), please let me know and I'll update the formulation.

[mkeintz]

One could program all combinations of 3 integers drawn from 1 through 10 - and then filter for those that sum to 20, which is how I understand many of the solutions.

But you could use a different strategy that step through only those that start out summing to 20.  The program below finds only triples where

1. x1<x2<x3, and     (I have a similar approach for x1<=x2<=x3 below).
2. sum(of x:)=20.

Once you've found these, you could get all the re-orderings of x1,x2,x3 if desired.

The strategy is

1. first find the minimum possible x1 and maximum possible x1 that could satisfy 1 and 2 above.
   1. The minimum is obviously 1
   2. The maximum has to be the floor of (20/3) minus 1.  Since 5+6+7=18 and 6+7+8=21 the maximum has to be 5.  (drop the minus 1 if re-use of integers is allowed: x1<=x2<=x3).
2. For each possible value of x1=1 to 5, get the maximum allowable value for X3.  That can be either 10, or 20-x1-(x1+1).  whichever is smaller (again adjustable for x1<=x2<=x3).
3. Calculate the corresponding X2
4. Then loop as long as x1<x2<x3 and sum(of x:)=20
   1. report the triple
   2. decrement x3 by 1 and increment x2 by 1

%let sum=20;
%let max_x=10;

data _null_;
  upper_limit1=floor(&sum/3)-1;

  length x1-x3 8;

  do x1=1 to upper_limit1;
    x3=min(&sum-x1-x1-1,&max_x); 
    x2=&sum-x1-x3;
    do while (x1<x2 and x2<x3);
      put (x1 x2 x3) (+2 z2.);
      x3=x3-1;
      x2=x2+1;
    end;
  end;
run;

Now if a number can be re-used, then minor modifications can be made:

%let sum=20;
%let max_x=10;

data _null_;
  upper_limit1=floor(&sum/3);  /* drop the "-1" */

  length x1-x3 8;

  do x1=1 to upper_limit1;
    x3=min(&sum-x1-x1,&max_x);    /*Change the 1st argument of MIN()*/
    x2=&sum-x1-x3;
    do while (x1<=x2 and x2<=x3);  /*Change "<" to "<=")*/
      put (x1 x2 x3) (+2 z2.);
      x3=x3-1;
      x2=x2+1;
    end;
  end;
run;

This is more "efficient" in that it never generates non-qualifying triples that would have to be filtered ot.  But I think it would be harder to generalize to more than 3 summands compared to most of the other suggestions.