Date: Mon, 3 Jan 2000 18:32:42 -0500 "Dorfman, Paul" "SAS(r) Discussion" "Dorfman, Paul" Re: combinatorial question... text/plain; charset="iso-8859-1"

Jeff,

As I understand the task now, you need to develop a DATA step routine that would accept N at run-time as a SAS variable, produce all possible N*N permutations, and print them. Although it is impossible to do with a macro assembling only a needed number of loops (as the number must be known beforehand), it is possible to accomplish using the 'dead code' approach. Namely, we can compile the step with a number of nested loops M exceeding any practically possible limit, say M=30 or M=50, and during run-time, make (M-N) innermost loops iterate only once by adjusting their upper bound. Since the upper bound of any loop can be a variable incorporated in an array, it is easy to disable exactly as many innermost loops as necessary depending on the value of N. For the sake of brevity, let us first let M <-- 9 and suppose that we want to print all 4*4 permutations:

data _null_; array h(9); array x(9); n = 4; do _i_=1 to 9; h(_i_) = (_i_ > n) + n*(_i_ le n); end; do x1=1 to h(1); do x2=1 to h(2); do x3=1 to h(3); do x4=1 to h(4); do x5=1 to h(5); do x6=1 to h(6); do x7=1 to h(7); do x8=1 to h(8); do x9=1 to h(9); do _i_=1 to n; put x(_i_) @@; end; put; end; end; end; end; end; end; end; end; end; run;

In other words, the upper limits of the innermost loops h5--h9 are set to unity, rendering them operative just once, whilst h1--h4 are set to 4, so these loops iterate through the full range from 1 to N; and only the variables x1--x4 actually get printed. Naturally, instead of hardcoding a routine with 30 or so nested loops, we can generate them with a macro supplying the _name_ of the governing run-time DATA step variable N as an argument:

%macro perm(n,lim=30); %local i; retain h1-h&lim . x1-x&lim .; hoffset = addr(h1) - 8; xoffset = addr(x1) - 8; do _i_=1 to &lim; call poke((_i_ gt &n)+&n*(_i_ le &n),hoffset + 8*_i_,8); end; %do i=1 %to &lim; do x&i=1 to h&i; %end; do _i_=1 to &n; prn_x = peek(xoffset + 8*_i_,8); put prn_x @@; end; put; %do i=1 %to &lim; end; %end; %mend perm;

Above, I had the audacity to replace the arrays with explicit addressing to avoid repetitive array definitions, if they are used inside the routine and the latter is called more than once in the same DATA step. RETAINs guarantee that the variables x1-x&lim and h1-x&lim reside in adjacent equidistant cells whose addresses are spaced 8 bytes from each other. Now, the macro can be invoked simply as

data _null_; n = 2; %perm(n); m = 3; %perm(m); z = 5; %perm(z); ... run;

and so on.

Kind regards, ============================ Paul M. Dorfman Citicorp Universal Card Jacksonville, Fl ============================

Jeff D. Hamann <hamannj@ucs.orst.edu>, in part, wrote:

>I forgot to mention that I don't know what the value of N at compile time. >That is to say how do I generate the combinations for N^N at run time.... > >Basically, how do I turn this.... > >void loop( unsigned long n ) >{ > unsigned long i, j, k; > unsigned long temp_start; > unsigned long temp_end; > for( i = 0; i < n; i++ ) > { > for( j = 0; j < i; j++ ) > { > for( j = 0; j < n; j++ ) > { > for( k = 0; k < n; k++ ) > { > fprintf( stdout, "%ld %ld %ld\n", i,j,k ); > } > } > } >} > >into some (hopefully not) recursive function that will generate all the >combinations?

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