[algogeeks] Re: check string A and B isPermutation ?

Fri, 14 Apr 2006 19:23:31 -0700

how about a randomized approach if the string is truly big. Generate *relatively* prime numbers for each character in string and compute the product. Repeat it N times to minimize the chances of error. It must easy to observe that as you increase N, your chances of error decreases.

On 4/14/06, Timak <[EMAIL PROTECTED]> wrote:

Gene,

If in reality space is no consern, I'd argue that just comparing
the histograms (what BigYan suggested, except that he tried to
optimize it) is the best approach.  It is O(2N) time and O(w) space,
while your proposal is O(2wN) time and O(N) space.  Copmaring the
histograms is also the simplest.

Timak

"Gene" < [EMAIL PROTECTED]> writes:

> Let's be real.  I can't imagine a application where it could make much
> of a difference.  Can you?
>
> Almost certainly it is simplicity and beauty and angels dancing on pins
> we're talking about.
>
> By the way, you can add about 16 characters to my function above and it
> becomes a true sort (not a sort into 1-hamming or gray code order).
>
>
>


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to