Date:         Mon, 15 Dec 2003 13:28:40 -0800
Reply-To:     "Choate, Paul@DDS" <pchoate@DDS.CA.GOV>
Sender:       "SAS(r) Discussion" <SAS-L@LISTSERV.UGA.EDU>
From:         "Choate, Paul@DDS" <pchoate@DDS.CA.GOV>
Subject:      Re: Permutation problem
Comments: To: LWn <villerwalle.nononospam@YAHOO.COM>

Hi Lars -

Fun problem!  When I had a combinatorics course a couple decades ago I was
taught to think of the factorial combinations as a path along a series of
branches.  In your case 720 is 6!=6*5*4*3*2*1.  To select a "path" one would
take the correct element from the n=6 group DGJLOU (in your case the second
letter) and then the correct letter from the remaining n=5 group DJLOU (in
your case the fourth letter), etc.  The path itself is determined by how 194
is obtained from the sum of n1*5!+n2*4!+ n3*3!+n4*2!+ n5*1!+n6*0!.  N6 is
multiplied by 0 because after the first five letters are chosen the sixth is
fixed.

Below are two brief do loops that 1) deconstruct the path with division and
integer truncation using the factorials, and then 2) select the six letters
from your set using substring and compression functions.  You can assign any
number from 0 to 719 to RANK and get that sequence from your set of paths.



%LET RANK=194;

data _null_;

R=&RANK-1;   /* 0 - 719 paths >> 00000 to 543210 */

ARRAY M M1-M5;
DO I = 1 TO 5;
   M{I}=INT(R/FACT(6-I)); /** remove 5!, 4!, etc. **/
   R=R-M{I}*FACT(6-I);
END;

WORD='DGJLOU';

ARRAY L $1 L1-L6;
DO I = 1 TO 5;
   L{I}=SUBSTR(WORD,M{I}+1,1);  /** pick letter path **/
   WORD=COMPRESS(WORD,L{I});
END;
   L6=SUBSTR(WORD,1,1);  /** The last letter **/

WORD=L1||L2||L3||L4||L5||TRIM(WORD);

PUT WORD;
RUN;


/*******   log output ******
GODJUL
NOTE: DATA statement used:
      real time           0.01 seconds
      cpu time            0.01 seconds
/******   log output ******/


I think that's a bit more elegant - Merry Christmas to you!


Paul Choate
DDS Data Extraction
(916) 654-2160

-----Original Message-----
From: LWn [mailto:villerwalle.nononospam@YAHOO.COM]
Sent: Sunday, December 14, 2003 12:52 PM
To: SAS-L@LISTSERV.UGA.EDU
Subject: Permutation problem

This week every year I use to present a small permutation problem in
two steps to my students.
i) How many possible sixletter "words" can be made using
the letters DGJLOU? No problem, the answer usually comes
within ten seconds.
ii) OK, now I want you to arrange all those 720 "words"
alphabetically. What "word" is number 194?

1:  DGJLOU
2:  DGJLUO
.
194:  ??????
.
720:  UOLJGD

If the students are familiar with SAS or some other programming
tool I ask them to try using their computers. Here is my SAS solution.
Does anybody have a more elegant solution with SAS or SPSS?

data dgjlou (keep=word) ;
  length i j k l m n $ 1. ;
  do i='D', 'G', 'J', 'L', 'O', 'U' ;
    do j='D', 'G', 'J', 'L', 'O', 'U' ;
      do k='D', 'G', 'J', 'L', 'O', 'U' ;
        do l='D', 'G', 'J', 'L', 'O', 'U' ;
          do m='D', 'G', 'J', 'L', 'O', 'U' ;
            do n='D', 'G', 'J', 'L', 'O', 'U' ;
              word = i||j||k||l||m||n ;
              xx = (i=j)+(i=k)+(i=l)+(i=m)+(i=n)
                  +(j=k)+(j=l)+(j=m)+(j=n)+(k=l)
                  +(k=m)+(k=n)+(l=m)+(l=n)+(m=n) ;
              xx = 0 then output ;
            end ;
          end ;
        end ;
      end ;
    end ;
  end ;
run ;
------------------------------
No 194 is GOD JUL which is Swedish for Merry Xmas!

/Lars Wahlgren
Lund university, Sweden