Providing software solutions since 1976
|
Generating Combinations and Permutations
(originally in SAS Communications 2nd Qtr 1992 p. 36+)
(modified 7/99 to allow negative and decimal numbers)
While the number of permutations and combinations of n items taken r at a time
is easy to calculate, generating the actual permutations and
combinations themselves takes a bit of coding. Following are two macros, %combo
and %permute, which will perform the respective generation.
To invoke one of the macros, simply provide the n elements, and r, as in:
%combo(r,item1,item2,item3, ... ,itemn)
%permute(r,item1,item2,item3, ... ,itemn)
where r is between 1 and n, inclusive. Some examples are:
%combo(2,a,b,c)
%permute(2,a,b,c)
which will generate all combinations of the three items a, b, and c taken 2 at a
time, and the permutations of the elements a, b, and c taken 2 at a
time. The items can be either character or numeric. Other valid invocations
follow.
%permute(2,Chip,Pete,Mike,William)
%combo(4,Chip,Mike,Nan,Greg,Bob,Owen)
Each of the macros begins with a 10-line section that utilizes the PARMBUFF
macro option and the %SCAN function to read the value of r,
the number of elements, and what the elements are. The basic idea behind the
%permute macro is to generate r variables, and let them each
loop through all n items. The above invocation would create the following loop:
do r1="Chip","Pete","Mike","William";
do r2="Chip","Pete","Mike","William";
The macro will check to see if r1 and r2 have the same value, and if they do
not, r1 and r2 will be saved as one permutation.
%macro permute(r) / parmbuff; /* the parmbuff option assigns */
%let i=2; /* the invocation parameter list to the */
%let things=; /* macro variable &syspbuff */
%do %while (%Qscan(&syspbuff,&i,%STR(,%))) ne ); /* scan the syspbuff */
%let p&i="%Qscan(&syspbuff,&i,%STR(,%)))"; /* to determine r */
%if &i=2 %then %let things=&&p&i; /* and count the number */
%else %let things=&things,&&p&i; /* of elements, n */
%let i=%eval(&i+1);
%end;
%let n=%eval(&i-2);
data permute;
drop i j copy;
array check (*) $ 10 r1-r&r; /* create a total of r */
%do m=1 %to &r; /* variables for looping */
do r&m = &things;
%end;
copy=0;
do i=2 to &r; /* look for duplicate items */
do j=1 to i-1; /* and keep the unique ones */
if check(j)=check(i) then copy+1;
end;
end;
if copy = 0 then output; /* writes to a SAS data set */
if copy = 0 then put r1-r&r; /* writes to the log */
%do m=1 %to &r;
end; /* end the r DO LOOPS */
%end;
run;
proc print uniform data=permute;
title "permutations of &n items taken &r at a time ";
run;
%mend permute;
Invoking the macro as shown above produces the following output:
permutations of 4 items taken 2 at a time
OBS R1 R2
1 Chip Pete
2 Chip Mike
3 Chip William
4 Pete Chip
5 Pete Mike
6 Pete William
7 Mike Chip
8 Mike Pete
9 Mike William
10 William Chip
11 William Pete
12 William Mike
The %combo macro is a little more complex. It also will create r variables,
however the values each of the variables takes on will depend on its
relative position with respect to the subscript on r. This is the loop that the
macro will create for the above invocation:
do r1=1 to 3;
do r2=r1+1 to 4;
do r3=r2+1 to 5;
do r4=r3+1 to 6;
Here the values of r1 through r4 will be a set of r subscripts of the relative
positions of the n items. The first time through the loop, r1=1, r2=2,
r3=3, r4=4, corresponding to the elements Chip, Mike, Nan, and Greg, since Chip
is the first item, Mike the second, Nan the third, and Greg the
forth. The very last time through the loop, r1=3, r2=4, r3=5, r4=6,
corresponding to the elements Nan, Greg, Bob, Owen. This looping will not
generate sets of subscripts with duplicate entries, and hence no item will
appear more than once for each combination. The subset of items
corresponding to each set of subscripts will be saved.
%macro combo(r)/parmbuff;
%let i=2;
%let things=;
%do %while (%Qscan(&syspbuff,&i,%STR(,%))) ne );
%let p&i="%Qscan(&syspbuff,&i,%STR(,%)))";
%if &i=2 %then %let things=&&p&i;
%else %let things=&things,&&p&i;
%let i=%eval(&i+1);
%end;
%let n=%eval(&i-2);
data combo;
keep v1-v&r;
array word $8 w1-w&n (&things);
array rr (*) r1-r&r;
array v $8 v1-v&r;
%do i=1 %to &r; /* create the DO LOOPs */
%if &i=1 %then %do;
do r&i=1 to &n-(&r-&i);
%end;
%else %do;
do r&i=r%eval(&i-1)+1 to &n-(&r-&i);
%end;
%end;
do k=1 to &r; /* select subscripted items */
v(k)=word (rr(k)); /* for a SAS data set */
put v(k) ' ' @; /* for log */
end;
put; /* writes to log */
output; /* writes to a SAS data set */
%do i=1 %to &r;
end; /* create ENDs for the DO LOOPs */
%end;
put;
run;
proc print uniform data=combo;
title "combinations of &n items taken &r at a time ";
run;
%mend combo;
Invoking the macro as above will generate the following output:
combinations of 6 items taken 4 at a time
OBS V1 V2 V3 V4
1 Chip Mike Nan Greg
2 Chip Mike Nan Bob
3 Chip Mike Nan Owen
4 Chip Mike Greg Bob
5 Chip Mike Greg Owen
6 Chip Mike Bob Owen
7 Chip Nan Greg Bob
8 Chip Nan Greg Owen
9 Chip Nan Bob Owen
10 Chip Greg Bob Owen
11 Mike Nan Greg Bob
12 Mike Nan Greg Owen
13 Mike Nan Bob Owen
14 Mike Greg Bob Owen
15 Nan Greg Bob Owen
Both macros give a choice of location for the results, either in a data set
using an output statement, or in the log (or file) with a put statement.
|
