```Date: Tue, 19 Dec 2000 16:31:38 -0500 Reply-To: "Bross, Dean S" Sender: "SAS(r) Discussion" From: "Bross, Dean S" Subject: Re: How to efficiently look up and classify permutations? Comments: To: "Vyverman, Koen" Content-Type: text/plain; charset="iso-8859-1" I can suggest one way to go about this problem. Go through the data set creating a new key which is derived by sorting the characters in WORD into order by their ASCII representation. This will have to be done with data step programming, breaking WORD into an array of numbers containing the ASCII values and writing out the statements to sort this array. Then rebuild the result into a new character string which is added to the data set. Then you can simply sort by this new character string. All combinations of WORD which are permutations of each other will sort together. You can use FIRST. and LAST. to put the results together in any way you'd like. Dean Bross Department of Veterans Affairs dean.bross@mail.va.gov -----Original Message----- From: Vyverman, Koen [mailto:koen.vyverman@FID-INTL.COM] Sent: Monday, December 18, 2000 12:53 PM To: SAS-L@LISTSERV.UGA.EDU Subject: Q: How to efficiently look up and classify permutations? LS, I'm currently faced with a quite daunting problem involving permut- ations. It appears daunting to me because _if_ there exists a clever solution, I fail to see it; and if not, it all becomes a matter of efficient coding, which is -- I admit -- not really my forte ;-) So, here's an appeal to the collective intellect of the SAS-L efficiency gurus: I have a number of SAS data sets containing 1 character variable WORD of length 51. The number of observations ranges from a few thousands up to about 90000. Within each data set, the values of WORD are unique and case-sensitive. They may contain up to 51 characters drawn from the following set of 56: the hyphen [-], the single straight quote ['], the forward and backward slashes [/\], the lowercase alphabet [a..z], and the uppercase alphabet [A..Z]. Blanks do not occur, and a given character may appear multiple times in the same WORD value. Data sets are unsorted. I wish to enhance each data set with a number of variables describing for each WORD value whether there exist other WORDs within the same data set that are identical to the current WORD, modulo a number of transpositions, i.e. swaps of two characters. The bit of code below will generate a sample data set WORK.WORDLIST to illustrate my purpose. The data are fake, but carefully chosen to highlight the issues in- volved: data wordlist; informat word \$51. swaps01-swaps03 5. found01-found03 \$500. ; input word= ; cards; word=moo swaps01=1 found01=omo word=omo swaps01=1 found01=moo word=roo word=Roo word=zoo swaps01=1 found01=ooz word=ooz swaps01=1 found01=zoo word=doc swaps01=2 found01=cod dco word=cod swaps01=1 found01=doc swaps02=1 found02=dco word=dco swaps01=1 found01=doc swaps02=1 found02=cod word=proc swaps01=2 found01=porc crop swaps02=1 found02=pocr word=porc swaps01=2 found01=proc pocr swaps03=1 found03=crop word=crop swaps01=1 found01=proc swaps03=2 found03=pocr porc word=pocr swaps01=1 found01=porc swaps02=1 found02=proc swaps03=1 found03=crop word=ya'-f swaps02=1 found02='ya-f word='ya-f swaps02=1 found02=ya'-f word=will-o'-the-wisp swaps01=1 found01=will-o-'the-wisp word=will-o-'the-wisp swaps01=1 found01=will-o'-the-wisp ; run; data wordlist(drop=i); set wordlist; array numz(i) _numeric_; do over numz; if numz=. then numz=0; end; run; How to read all this? Consider e.g. the first two obs. They form a sub- group having length 3 and consisting of the same characters in the same quantities: one 'm' and two times 'o'. Hence they can be mapped onto one another by means of a permutation which in its turn consists of a number of successively applied character swaps. This is detailed in the SWAPSnn and FOUNDnn variables. For 'moo', SWAPS01=1 tells us that one word was found that can be transformed into 'moo' by just one swapping operation. FOUND01 tells us what it is: 'omo'. If more than one word needs to go into a FOUNDnn variable, they should be separated by a space. The SWAPSnn variables are not essential, as one could simply count space-delimited words in the corresponding FOUNDnn values, but it would be nice to have them actually. Obviously, 'omo' can also be transformed into 'moo' by applying more than 1 transposition. This however is of no interest: the SWAPSnn and FOUNDnn variables should precisely partition the elements of the sub- group the current WORD is in (without listing the WORD itself, that is). As hinted at in the above, what I call 'sub-group' is a subset of the word-list containing those words having exactly the same character content. Thus, e.g. the sub-group consisting of 'proc', 'porc', 'crop', and 'pocr' has its SWAPSnn variables adding up to 3 for each of its con- stituent words. In general, each member of a sub-group with n members should have the sum of its SWAPS variables equalling n-1. Note that due to the case distinction, 'roo' and 'Roo' form distinct sub-groups ... The idea is to start with the data set WORDLIST having only the WORD variable, and to add only as many SWAPSnn and FOUNDnn variables to it as is strictly necessary. Note that, since the maximal word-length is 51, we might potentially need to add as many as 50 SWAPSnn and 50 FOUNDnn variables. As can be seen from the desired output WORDLIST, although the maximum word-length there is 16 (last 2 obs), only SWAPS01- SWAPS03 and FOUND01-FOUND03 were added, since nothing was found that takes more than three swapping operations anyway ... BTW, the last two obs should discourage any solutions that scale with the factorial of the word-length :-) (just try to imagine 50!) A word on the context of all this: it's basically part of a data scrub- bing exercise. I have vast quantities of manually entered data here, with substantial numbers of typos lurking inside. Professional typists will most of the time hit the right keys, but not always in the correct order. I'm trying to build a tool that will allow a worker to easily spot potential mistakes by showing what permutations of any given word appear in the wordlist. The environment is SAS 8.1 on WinNT. Plenty of disk space, plenty of RAM, but not an infinity of time :-) Anyone willing to give this one a try? Kind Regards, Koen Vyverman. ```

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