Date: Tue, 9 Jun 1998 13:11:55 -0400
Reply-To: "H. Mark Keintz" <mkeintz@POP.UPENN.EDU>
Sender: "SAS(r) Discussion" <SAS-L@UGA.CC.UGA.EDU>
From: "H. Mark Keintz" <mkeintz@POP.UPENN.EDU>
Subject: Re: Word Jumble problem
In-Reply-To: <SAS-L%98060517561269@UGA.CC.UGA.EDU>
Content-Type: TEXT/PLAIN; charset=US-ASCII
There have been a number of solutions to the word jumble problem, but I
don't think I saw any that would not require reprogramming when the word
to be jumbled gets longer or shorter. Below are solutions to two more
general permutation problems.
Problem 1: Generate all permutations of a character string. My proposal
is in program 1 below. It's main features are:
1. It uses the COMPRESS function to update the string being permuted.
Because COMPRESS removes **all** instances of a character (or
characters) from a string, the program never needs to test whether
a character has been drawn more than once from the source sting
(which many of the other proposals need to do). NOTE that this also
means that the program purges source string of duplicates first, so
as not to generate an inappropriate number of permutations.
2. As I mention above, the algorithm used will treat a character string
of any length.
3. Simply changing the %LET command in program 1 is all that is required
to generate an appropriate collection of permuted strings.
Problem 2: Generate a specified permutation of a character string. My
proposal is in program 2 below, along with a DATA step demonstrating its
use. It's main features:
1. It uses a macro (GETPERM) to generate the result, although I believe
the code could easily by put into ordinary SAS code.
2. It also uses the COMPRESS function. Unlike program 1, this macro
does not check for duplicate characters, since that would be the task
of the calling program.
3. The GETPERM macro takes either literal or variable arguments. These
are demonstrated in the sample DATA step.
In addition to leveraging the power of the COMPRESS function, these
programs also generate one possible mapping of permutations onto an index
set. I.e., if we know there are 24 permutations of "abcd", this provides
a way to assign each to a "permutation number."
/********************************** PROGRAM 1 *******************************/
******* Procedure to generate all permutations of a character string *******;
** Note the following assumption: **;
** 1. The original character string has no duplicate characters. **;
** Usage: **;
** 1. Change the %let command below to the string of your choice. **;
** 2. You may wish to change the put= to an output command. **;
** Notes: **;
** 1. The loop that goes P=0 to NPERM-1 would work as P=1 to NPERM too. **;
** **;
** mkeintz@pop.upenn.edu 6/9/98 **;
*****************************************************************************;
%let original=abcef;
data _null_;
orig="&original"; *Put word to be permuted in orig;
result=orig; result=" "; *Make a same-length blank character variable;
nlet=length(orig); *Calculate the number of letters to be drawn;
nperm=1; *Calculate the number of permutations to
generate;
do i=1 to nlet; *this could easily be macro-ized to a command
...;
nperm=nperm*i; * ... like nperm=%nperm(n);
end;
do p=0 to nperm-1; *For each permutation P... ;
string=orig; *Generate a working string;
result=" "; *blank out result from previous
permutation;
do i = nlet to 1 by -1; *For each letter .... ;
letr=substr(string,mod(p,i)+1,1); *Draw a letter indicated by P ;
result=left(trim(result) || letr); *Stick it in the result ;
string=compress(string,letr); *Remove it from the working string;
end;
put p= result=; * or OUTPUT, etc. ;
end;
run;
/********************************** PROGRAM 2 *******************************/
********** GETPERM generates the P'th permuation of a character string ******;
** Note the following assumption: **;
** 1. The original character string has no duplicate characters. **;
** Usage: **;
** 1. %getperm("abcd",p) or %getperm(word,p) **;
** where word is a character var **;
** and p is a number or a numeric variable. **;
** Notes: **;
** 1. I had wanted to generate a macro that would work in the following **;
** way. RESULT=%GETPERM("abcd",4), but the lack of an exact macro **;
** analog to the COMPRESS function prevents it. **;
** 2. Note that P can be ANY positive or negative number. The macro **;
** will simply cycle through all possible permutations **;
** **;
** mkeintz@pop.upenn.edu 6/9/98 **;
*****************************************************************************;
%macro getperm(orig,p); *Macro to generate the Pth permutation of orig;
start=&orig; *Make a working string variable;
nlet=length(start); *How many letters to jumble?;
result=&orig; result=" "; *Build a same-length blank variable;
do i = nlet to 1 by -1; * ... for
letr=substr(start,mod(&p,i)+1,1);
result=left(trim(result) || letr);
start=compress(start,letr);
end;
%mend getperm;
/*********** Sample use of GETPERM follows */
data _null_;
wrd="abcd";
do p=0 to 24;
%getperm(wrd,p);
put p= result= ;
end;
%getperm(wrd,100); put p= result=;
do p=4 to 7;
%getperm("efgh",p);
put p= result=;
end;
%getperm("wxyz,22); put p= result=;
run;
Mark Keintz University of Pennsylvania / 6298
Computer Core Director Population Studies Center
mark_keintz@pop.upenn.edu 3718 Locust Walk
phone: 215/898-6713 fax: 898-2124 Philadelphia, PA 19104-6298
