Date: Mon, 17 Mar 2008 17:32:04 -0500 "Richard A. DeVenezia" "SAS(r) Discussion" "Richard A. DeVenezia" Re: n choose k problem To: Stefan Pohl text/plain; charset="iso-8859-15"

Stefan Pohl wrote: > Dear sas-list, > > is there an easy way to get all n choose k possibilities. > > For example: > > I have persons 1 2 3 4 5 6 7 8 9 10 > > I want to build groups of 6 persons. The groups are separated by |. > One possibility could be: 1 2 | 3 4 | 5 | 6 | 7 8 | 9 10 > > In the example there are 9 choose 5 of such possibilities. > > How do I get a dataset with all n choose k possibilities?

There are routines ALLPERM RANPERM and RANCOMB, ... but no ALLCOMB. You can generate all combinations using nested loops.

But you are really working on a couple of levels here.

First, there are five ways to break 10 items into 6 groups.

A: 1 1 1 1 1 5 B: 1 1 1 1 2 4 C: 1 1 1 1 3 3 D: 1 1 1 2 2 3 E: 1 1 2 2 2 2

You example, restated, would be a member of E 5 | 6 | 1 2 | 3 4 | 7 8 | 9 10 If the permutation of the breakdowns are significant, your problem space just got alot bigger.

Let COMB(n,m) be shorthanded as nCm The number of arrangements being

A: 10.9.8.7.6 B: 10.9.8.7.6c2 C: 10.9.8.7.6c3 D: 10.9.8.7c2.5c2 E: 10.9.8c2.6c2.4c2

In general n C i[1] . (n-i[1]) C i[2] . (n-i[1]-i[2]) C i[3] ...

Writing SAS code to traverse this space is not impossible and not trivial.

-- Richard

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