Date:         Mon, 13 Dec 2010 23:09:02 -0800
Reply-To:     Daniel Nordlund <djnordlund@FRONTIER.COM>
Sender:       "SAS(r) Discussion" <SAS-L@LISTSERV.UGA.EDU>
From:         Daniel Nordlund <djnordlund@FRONTIER.COM>
Subject:      Re: code, find all combinations
In-Reply-To:  <000201cb9b48$21a5b690$64f123b0$@com>
Content-Type: text/plain; charset="UTF-8"

> -----Original Message-----
> From: SAS(r) Discussion [mailto:SAS-L@LISTSERV.UGA.EDU] On Behalf Of
> bbser2009
> Sent: Monday, December 13, 2010 8:34 PM
> To: SAS-L@LISTSERV.UGA.EDU
> Subject: code, find all combinations
>
> I wrote a specific code finding all samples of size 3 from the population
> consisting of 1, 2 ,3, 4.
> The idea is direct:
> First get data set like this, no repeated values in each observation.
> 1 2 3
> 2 4 3
> 2 1 3
> ...
>
> Then bubble-sort each observation from small to big.
> 1 2 3
> 2 3 4
> 1 2 3
> ...
>
> Next by-group observations that are identical with each other.
> 1 2 3
> 1 2 3
> ...
> 2 3 4
> 2 3 4
> ...
>
> At last, output the last observation of each by-group to get all the
> samples.
> 1 2 3
> 1 2 4
> 1 3 4
> 2 3 4
> (For code, see bottom)
>
> Apparently this algorithm/code is hard to generalize.
> So I am curious about how people have addressed this issue in a more
> general
> way?
> I guessed the general algorithm had to be complicated.
> By any chance, however, does anyone know at least what key ideas lay
> behind
> it?
> Any comments are welcome!
>
> Thanks.
>

Max,

This question comes up regularly. The algorithm really isn't all that complicated.  Here is one solution.  It is a macro that writes a data step which outputs one record per combination into a dataset called COMB.  This will work ok when n and k are not too big.  Just be careful about combinatorial explosion.  There are other solutions as well.  If one has SAS STAT then I would probably recommend using PROC PLAN.

%macro comb(n,k);
  data comb;
  %let k0=;
    k0 = 0;
     %do i = 1 %to &k;
        do k&i = k%eval(&i-1) +1 to %eval(&n-&k+&i)%str(;);
     %end;
               output;
     %do i = 1 %to &k;
        end%str(;);
     %end;
  drop k0;
  run;
%mend;

%comb(4,3)

Hope this is helpful,

Dan

Daniel Nordlund
Bothell, WA USA