Re: Detecting transpositions

Efficiency is paramount.

Have you considered precomputing transpositions?

Then, comp(A, B) becomes

lookup A' (the set of transpositions for A)
determine if B is a member of A'

If everything is in a big hash (i.e., if you've traded space for time), the lookup is quick. You could even do a lazy initialization of the transposition set.

Comment on Re: Detecting transpositions Download Code

Replies are listed 'Best First'.
Re: Re: Detecting transpositions by BrowserUk (Patriarch) on Aug 06, 2003 at 22:00 UTC
That really helps. Kind of like a lazy evaluating ST. The problem remains O9nn!), but for n-1 n! passes the comp() comes down to `return $cache{$_[0]}{$_[1]} if exists $cache{$_[0]}{$_[1]};` [download] Which is a huge time saver (provided I don't run out of memory:). Thanks. Examine what is said, not who speaks. "Efficiency is intelligent laziness." -David Dunham "When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller If I understand your problem, I can solve it! Of course, the same can be said for you.	[reply] [d/l]
Re: Re: Detecting transpositions by chanio (Priest) on Aug 07, 2003 at 02:30 UTC
shouldn't you sum up the weight of every character first to compare the result and know if they have the same ones?	[reply]