Today I faced the problem of needing to generate all r-sized combinations from n elements, good old n choose r.

I found it annoyingly hard to either solve the problem or find code for it; most solutions were in something like Python and used special libraries specific to the given language.

Finally I found an algorithm from Kenneth H. Rosen, Discrete Mathematics and Its Applications. There is a Java program at http://www.merriampark.com/comb.htm, and I have translated it into SAS. Herewith, a solution looking for a problem.

*-- compute n choose r combinations. Get the actual combinations, not how many there are. ;

%let n = 7; %let r = 3;

data combinations(keep = result); array a(0:%eval(&r - 1)) _temporary_; /*subscripts into elements array*/ array elements(0:%eval(&n-1)) $ ("a" "b" "c" "d" "e" "f" "g");

total = comb(&n, &r);

do i = 0 to dim(a) -1; a(i) = i; end;

numLeft = total;

do hasMore = total to 1 by -1; if numLeft = total then do; link doSomething; numLeft = numLeft - 1; continue; end;

i = &r - 1; do while (a(i) = &n - &r + i); i = i - 1; end;

a(i) = a(i) + 1;

do j = i + 1 by 1 while (j < &r); a(j) = (a(i) + j) - i; end;

numLeft = numLeft - 1; link doSomething; end;

stop; doSomething: Length result $ 20; do j = 0 to dim(a) -1; result = catx(" ", result, elements(a(j))); end; output; result = " "; return; proc print;

For this case, seven choose three, the results of the print are:

Obs result

1 a b c 2 a b d 3 a b e 4 a b f 5 a b g 6 a c d 7 a c e 8 a c f 9 a c g 10 a d e 11 a d f 12 a d g 13 a e f 14 a e g 15 a f g 16 b c d 17 b c e 18 b c f 19 b c g 20 b d e 21 b d f 22 b d g 23 b e f 24 b e g 25 b f g 26 c d e 27 c d f 28 c d g 29 c e f 30 c e g 31 c f g 32 d e f 33 d e g 34 d f g 35 e f g