topic Re: getting all combinations which sum =100 in SAS Programming

getting all combinations which sum =100

tom12122 — Fri, 06 Apr 2012 12:07:29 GMT

I need to get all combinations of all variables with domain (from incl. 0 to 100 incl. step 10 - namely 0,10,20,30,40.... 100) but only those sets which sum =100 (eg. for 6 variables one of combinations would be getting all combinations which sum =100)

I know that there's an allcomb function that does exacly that but i returns combinations without that condition and this condition dramatically decreases combinations returned.

Maybe an option is recurrsive FCMP function but I don't know how to write that in SAS.

Help would be appriciated

Re: getting all combinations which sum =100

ballardw — Fri, 06 Apr 2012 21:39:02 GMT

I suggest that you post an abbreviated example of your data, variables and desired output. Are you looking at a total of variables within a single record or across multiple records? How many variables do you have. Are all values positive? How do variables with missing values get treated? Values of 0?

Your mention of a domain of 0 to 100 by 10 does not look like a request for variables but of values, which would be an entirely different beast.

Re: getting all combinations which sum =100

PGStats — Sat, 07 Apr 2012 01:51:32 GMT

Find all the possible splits in the sequence 1,...,10 and count their sizes. Then, eliminate duplicates. The result is expressed as n1 = the number of ones, n2 = the number of twos, etc. In theory, it will work for N up to 63, but I wouldn't try it with N>20 :

data comb(keep=n:);
array n{*} n1-n10;
format n: 2.;
length c $9 b $1;
do k = 0 to 2**(10-2)-1;
c = put(k, binary9.);
do b = "0", "1";
do i = 1 to 10; n{i} = 0; end;
j = 1;
do i = 1 to 9;
   if char(c, i) = b then do;
    n{j} + 1;
    j = 0;
   end;
   j + 1;
end;
n{j} + 1;
output;
end;
end;
run;

proc sort data=comb nodupkey; by n:; run;

proc print data=comb; run;

-------------------------------------------------------------

The SAS System 20:50 Friday, April 6, 2012 1

Obs n1 n2 n3 n4 n5 n6 n7 n8 n9 n10

                     1     0     0     0     0     0     0     0     0     0     1
                     2     0     0     0     0     2     0     0     0     0     0
                     3     0     0     0     1     0     1     0     0     0     0
                     4     0     0     1     0     0     0     1     0     0     0
                     5     0     0     2     1     0     0     0     0     0     0
                     6     0     1     0     0     0     0     0     1     0     0
                     7     0     1     0     2     0     0     0     0     0     0
                     8     0     1     1     0     1     0     0     0     0     0
                     9     0     2     0     0     0     1     0     0     0     0
                    10     0     2     2     0     0     0     0     0     0     0
                    11     0     3     0     1     0     0     0     0     0     0
                    12     0     5     0     0     0     0     0     0     0     0
                    13     1     0     0     0     0     0     0     0     1     0
                    14     1     0     0     1     1     0     0     0     0     0
                    15     1     0     1     0     0     1     0     0     0     0
                    16     1     0     3     0     0     0     0     0     0     0
                    17     1     1     0     0     0     0     1     0     0     0
                    18     1     1     1     1     0     0     0     0     0     0
                    19     1     2     0     0     1     0     0     0     0     0
                    20     1     3     1     0     0     0     0     0     0     0
                    21     2     0     0     0     0     0     0     1     0     0
                    22     2     0     0     2     0     0     0     0     0     0
                    23     2     0     1     0     1     0     0     0     0     0
                    24     2     1     0     0     0     1     0     0     0     0
                    25     2     1     2     0     0     0     0     0     0     0
                    26     2     2     0     1     0     0     0     0     0     0
                    27     2     4     0     0     0     0     0     0     0     0
                    28     3     0     0     0     0     0     1     0     0     0
                    29     3     0     1     1     0     0     0     0     0     0
                    30     3     1     0     0     1     0     0     0     0     0
                    31     3     2     1     0     0     0     0     0     0     0
                    32     4     0     0     0     0     1     0     0     0     0
                    33     4     0     2     0     0     0     0     0     0     0
                    34     4     1     0     1     0     0     0     0     0     0
                    35     4     3     0     0     0     0     0     0     0     0
                    36     5     0     0     0     1     0     0     0     0     0
                    37     5     1     1     0     0     0     0     0     0     0
                    38     6     0     0     1     0     0     0     0     0     0
                    39     6     2     0     0     0     0     0     0     0     0
                    40     7     0     1     0     0     0     0     0     0     0
                    41     8     1     0     0     0     0     0     0     0     0
                    42    10     0     0     0     0     0     0     0     0     0

Re: getting all combinations which sum =100

Ksharp — Mon, 09 Apr 2012 04:02:07 GMT

As ballardw said, You need post some sample data to clarify your problem more .

Ksharp

Re: getting all combinations which sum =100

manojinpec — Mon, 09 Apr 2012 05:10:05 GMT

Example please?

Re: getting all combinations which sum =100

tom12122 — Tue, 10 Apr 2012 09:12:12 GMT

For example - I need all combinations of 3 variables v1, v2, v3 (each can be either of these values: 0,10,20,30,40.... 100) but only combinations in which v1+v2+v3 =100

v1 v2 v3 sum

10 80 10 100 - OK

10 90 10 110 - I don't want this combiantion

30 30 40 100 -OK

This is an example. I need to have possibility to make combinations for N variables. The clue is not to make all combinations and afterwards eliminating those that don't meet conditions - the number of all combinations is much greater then the number of combinations with sum=100 - So during generation of combinations sum should be checked to optimize generation time.

Re: getting all combinations which sum =100

LinusH — Tue, 10 Apr 2012 09:56:41 GMT

Is this a real life problem? Seems kind of odd...

If you plan to create you combinations within a data step, you could use a subsetting if with the sum() function.

If you var1-varn uses such naming convention you can easily use the sum(of..) construct. Otherwise, link your variables to an array, which you then sum up.

if sum(of v:) = 100;

Re: getting all combinations which sum =100

PGStats — Tue, 10 Apr 2012 15:10:22 GMT

As I have shown above, there is no need to check the sum at generation time if all integers are allowed in the combination; you only need to figure out all the possible subsets of integers between 1 and 10. What I don't understand is what kind of advantage you may gain in having that set of possible combinations. Checking that a given combination is a member of the set is a lot more expensive than simply checking the sum.

Re: getting all combinations which sum =100

Astounding — Tue, 10 Apr 2012 15:38:34 GMT

Linus, I've seen something like this as a real-life problem. Given up to 20 recent transactions, find any combinations that sum to 0. The idea is that some transactions may be refunds for a combination of other purchases. You need to match the refund to the purchases.

At any rate, here's an approach simplified for 3 variables. The idea is to find combinations of v1-v3 that sum to 100.

do in1 = 'OUT', 'IN';

do in2 = 'OUT', 'IN';

do in3 = 'OUT', 'IN';

total = v1 * (in1='IN') + v2 * (in2='IN') + v3 * (in3='IN');

if total=100 then output;

end;

You can always switch to arrays if the number of variables becomes large. But note that your program canl chug for a while as the number of variables increases.

If you have to, you can always place this code inside a set of loops like this:

do v1=0 to 100 by 10;

do v2=0 to 100 by 10;

do v3=0 to 100 by 10;

** Above code;

end;

I'm just not certain whether this is part of the problem though.

Good luck!

Re: getting all combinations which sum =100

tom12122 — Tue, 10 Apr 2012 16:47:29 GMT

The problem is that I need to calculate that with given number of variables. I need a macro that has N-variables parameter on entry. In that case depending on N I will have N loops

Re: getting all combinations which sum =100

tom12122 — Tue, 10 Apr 2012 16:48:47 GMT

It is helpful with 10 or 15 variables - then the full number of combinations would be 10^10 and 10^15 respectively and with given sum the number decreases dramatically.

Re: getting all combinations which sum =100

PGStats — Tue, 10 Apr 2012 16:59:11 GMT

Actually, the number of combinations to consider is 2^9 or 2^14. Large numbers indeed, but feasable. There is a way to generate unique combinations directly, I'm quite sure. But that's a lot of intricate programming.

Re: getting all combinations which sum =100

Astounding — Tue, 10 Apr 2012 17:39:23 GMT

tom,

If I understand the problem correctly this time, you always want to get the sum of all N variables. That's relatively easy for a macro to generate, but as you have noted it may involve a great number of combinations.

Assuming you have a parameter &N with the number of variables, this belongs inside a macro definition:

%local i;

%do i=1 %to &N;

do v&i = 0 to 100 by 10;

%end;

if sum (of v1-v&N)=100 then output;

%do i=1 %to &N;

end;

%end;

Good luck.

Re: getting all combinations which sum =100

PGStats — Tue, 10 Apr 2012 21:04:23 GMT

If you have SAS/OR, you should notice that your problem is an integer cutting stock problem and exploit the solutions provided by proc clp. Try for instance :

proc clp findall out=soln;

variable (x1-x4) = [0,10];

linear x1 + x2 + x3 + x4 = 10;

run;

proc print data=soln; run;

Re: getting all combinations which sum =100

Ksharp — Wed, 11 Apr 2012 06:12:55 GMT

The simplest way is using Array+ do loop .

data have;
input v1 v2 v3 ;
cards;
10 80 10  
10 90 10 
30 30 40
;
run;
data want;
 set have;
 array _v{*} v1 v2 v3;
 do i1=1 to dim(_v);
  do i2=i1+1 to dim(_v);
   do i3=i2+1 to dim(_v);
    if sum(_v{i1},_v{i2},_v{i3}) eq 100 then output;
   end;
  end;
end;
run;

Ksharp

Re: getting all combinations which sum =100

tom12122 — Wed, 11 Apr 2012 08:37:36 GMT

works thank, but is there a possibility to enter near linear some generic contraint with meaning: sum of all x variables like: linear sum (x

) = 10 or similar?

Then I wouldn't have to generate dynamically constraint with dynamic number of variables. I will have N variables - N can change and will be a input parameter of a macro.

Re: getting all combinations which sum =100

tom12122 — Wed, 11 Apr 2012 08:45:38 GMT

There's something wrong with the syntax. Which ones should be of macro style (%if) and which of data step style (without %)? As far as i know if you change "if sum (of v1-v&N)=100 then output;" to macro style then you can't do arithetics.

Thanks for help anyway.

Re: getting all combinations which sum =100

shivas — Wed, 11 Apr 2012 08:55:39 GMT

Hi,

Try this

/*Example from SAS documentation*/

data test1;

array x[11] (0 10 20 30 40 50 60 70 80 90 100);

array c[3] ;

array i[3];

n=dim(x);

k=dim(i);

/* i[1]=0;*/

ncomb=comb(n,k);

do j=1 to ncomb+1;

call allcombi(n, k, of i

);

do h=1 to k;

c=x[i];

end;

if sum(of c1-c3)=100 then output;

end;

keep c1 c2 c3;

run;

or...

data test2;

do i =0 to 100 by 10;

do j=0 to 100 by 10;

do k=0 to 100 by 10;

if sum(i,j,k) =100 then output;

end;end;end;

run;

Thanks,

Shiva

Re: getting all combinations which sum =100

tom12122 — Wed, 11 Apr 2012 11:41:17 GMT

hm..

variable 1 - 10 combinations

variable 2 - 10 combinations

...

variable n - 10 combinations

then alltogether 10*10 * .... = 10^n without sum condition ? Am I wrong?

Re: getting all combinations which sum =100

PGStats — Wed, 11 Apr 2012 14:38:26 GMT

Look at it this way, any solution to the problem, say 20+60+20=100, has the form 10+10,10+10+10+10+10+10,10+10. Between each 10 there is either a + or a comma; there are 9 such positions, thus 2^9 possible solutions. You may retain all these 512 solutions, or decide to eliminate permutations such as (60,20,20), (20,60,20) and (20,20,60), in which case you are left with 42 unique solutions (see my first post).