From: David Kastrup Date: 2007-03-20T05:20:06+09:00 Subject: Re: Just for fun... "Trans" writes: > On Mar 15, 2:33 pm, "Matthew Moss" > wrote: >> On 3/15/07, Stephen Lewis wrote: >> >> > Matthew Moss wrote: >> > > +5 pts if you know what algorithm is being used here... >> >> > I'm not going to try to golf it right now, but it looks like an inverse >> > Burrows-Wheeler Transform. >> >> +5 for Stephen. =) > > Looks interesting. Care to elaborate on "inverse Burrows-Wheeler > Transform"? The Burrows-Wheeler transform takes some arbitrary string, say, gigantomania and sorts the permutations: we start with gigantomania igantomaniag gantomaniagi antomaniagig ntomaniagiga tomaniagigan omaniagigant maniagiganto aniagigantom niagigantoma iagigantoman agigantomani and then sort the lines: agigantomani aniagigantom antomaniagig gantomaniagi gigantomania iagigantoman igantomaniag maniagiganto niagigantoma ntomaniagiga omaniagigant tomaniagigan Then we take the last column and assign numbers to it: imgiangoaatn 0123456789AB Now we sort the letters with the numbers alongside. aaaggiimnnot 489260315B7A And now we walk off a linked list starting at 4 (we need to remember that starting position since all cyclic strings have the same BWT transform otherwise). That puts out the original sequence. -- David Kastrup, Kriemhildstr. 15, 44793 Bochum