Date:         Mon, 6 Jan 1997 14:16:05 EDT
Reply-To:     whitloi1@WESTATPO.WESTAT.COM
Sender:       "SAS(r) Discussion" <SAS-L@UGA.CC.UGA.EDU>
From:         Ian Whitlock <whitloi1@WESTATPO.WESTAT.COM>
Subject:      Re: Enumeration of a Permutation
Comments: To: Tim Browning <timbrowning@CONSULTEC-INC.COM>

    Subject: Enumeration of a Permutation
    Summary: Code suggested.
    Respondent: Ian whitlock <whitloi1@westat.com>
 
    Tim Browning <timbrowning@CONSULTEC-INC.COM> asked how to find all
    permutations of a set of letters.  The following message bounced, so I
    post it publicly.
 
    Tim,
 
    Here is one quick answer.  The first DATA step illustrates the code
    pattern.  Then a macro MKDO is written to write this pattern.  Then a
    DATA step uses the macro to reproduce the first code.  You could go
    further and build a macro to manage MKDO, but I didn't see the
    advantage here.  The generalization to 12 is obvious.  Note that for 12
    distinct letters there are over 479 million permutations of the
    letters, so don't expect the DATA step to end any time soon.  You may
    also run into trouble trying to print this many values.
 
    data _null_ ;
       array x (4) $ 1 _temporary_ ( 'a' 'b' 'c' 'd' ) ;
       do i1 = 1 to dim ( x )  ;
          do i2 = 1 to dim ( x ) ;
             if i2 ^= i1 then
             do i3 = 1 to dim ( x ) ;
                if i3 ^= i1 & i3 ^= i2 then
                do i4 = 1 to dim ( x ) ;
                   if i4 ^= i1 and i4 ^= i2 and i4 ^= i3 then
                   do ;
                      y = x(i1) || x(i2) || x(i3) || x(i4) ;
                      put y= ;
                   end ;
                end ;
             end ;
          end ;
       end ;
    run ;
 
    %macro mkdo ( i ) ;
        %local j ;
        do i&i = 1 to dim ( x ) ;
           if  i&i ^= i1
               %do j = 2 %to &i - 1 ;
                  and i&i ^= i&j
               %end ;
           then
    %mend mkdo ;
 
    data _null_ ;
       array x (4) $ 1 _temporary_ ( 'a' 'b' 'c' 'd' ) ;
       do i1 = 1 to dim ( x )  ;
          %mkdo ( 2 )
          %mkdo ( 3 )
          %mkdo ( 4 )
             do ;
                y = x(i1) || x(i2) || x(i3) || x(i4) ;
                put y= ;
             end ;
          end ;
          end ;
          end ;
       end ;
    run ;
 
    If you search the archives using "permutation" you should find numerous
    past discussions of this topic.  You might also try "combination".
 
    Ian Whitlock <whitloi1@westat.com>
 
 
______________________________ Reply Separator _________________________________
Subject: Enumeration of a Permutation
Author:  Tim Browning <timbrowning@CONSULTEC-INC.COM> at internet-e-mail
Date:    1/4/97 4:44 AM
 
 
I have a vexing challenge which I think I can solve (actually have
solved) but I would like to see other/alternative approaches.
 
This is the problem:  You want to read a character string such as "ABC"
and have a program print out all permutations (arrangements) of the
letters.
 
Example:
   input string is "ABC"
   program prints out ABC, CBA, CAB, ... etc.
 
In my specific case, there are 12 letters.
 
Any help would be most appreciated.
 
Thanks.
 
-----------------------------------------------------------
Tim Browning           Voice: 770-594-7799 ext. 8353
Consultec, Inc.          Fax: 770-410-0700
9040 Roswell Road,    E-mail: tim.browning@consultec-inc.com
Suite 700                     timprobe@mindspring.com
Atlanta, GA 30350
USA
---------------------------------------------------------------