I agree with much of what you say! I just think character sorting into
hamming-1 order is cool, especially since it generalizes to a true sort
with just a slight modification.
There are a few other things to think about however.
First, "simplest" depends on environment. In perl you can compare two
strings $a and $b with
if (join('', sort(split '', $a)) eq join('', sort(split '', $b)) {
# a is a permutation of b!
}
Histogram code would be more complex and would probably run slower.
Another thing is that it's meaningless to talk about O(2N) because
O(2N)=O(N).
Finally, for characters of w bits, the histogram requires O(2^w log N)
space in the general case, not O(w) as you say.
Moreover, run time is also O(2^w) to compare those histograms. For
example, if you are working in Unicode where characters might have up
to 4 bytes, you'd need 4 billion histogram entries (perhaps 16
gigabytes), and it would take a while to compare these.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
