Date:         Tue, 25 Oct 2005 22:47:44 -0400
Reply-To:     Arthur Tabachneck <art297@NETSCAPE.NET>
Sender:       "SAS(r) Discussion" <SAS-L@LISTSERV.UGA.EDU>
From:         Arthur Tabachneck <art297@NETSCAPE.NET>
Subject:      Re: Generate all Combinations
Comments: To: sas-l@uga.edu

jl,

Free advice: when facing such a problem, search the sas-l archives first.  I
searched them, via google, for the keyword 'combinations' and found the
following thread with a solution provided in the first article:
http://xrl.us/h68i

Art
-------
<jlgoldberg@brick.net> wrote in message
news:1130286174.206173.70700@g47g2000cwa.googlegroups.com...
> 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
>