```Date: Tue, 25 Oct 2005 22:47:44 -0400 Reply-To: Arthur Tabachneck Sender: "SAS(r) Discussion" From: Arthur Tabachneck 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 ------- 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 > ```

Back to: Top of message | Previous page | Main SAS-L page