Padmanabhan, can you elaborate a bit on your suggestion?
"Padmanabhan Natarajan" <[EMAIL PROTECTED]> writes:
> 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 t
Timak wrote:
> Yeah, I mistakenly swaped the true and false.
>
> My code works, but it assumes that you know that the lengths of the
> strings are the same.
I see what you're saying now. Thanks.
--~--~-~--~~~---~--~~
You received this message because you are su
Yeah, I mistakenly swaped the true and false.
My code works, but it assumes that you know that the lengths of the
strings are the same. BTW, the lengths could be calculated on the
fly. Also the hist doesn't have to be a vector, it could be a hash,
as you mentioned.
Here's a full c++ implementa
Timak wrote:
> Hey, I think it's cool too :-) BTW, how exactly do you generalize it?
Well, I'm going to let that as a puzzle for Algorithm Geeks! It's
equally cool. And I've never seen it published anywhere.
>
> > There are a few other things to think about however.
> >
> > First, "simplest"
Timak <[EMAIL PROTECTED]> writes:
>> 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.
>
> My bad. I should be paying more careful when I post. I meant
> O(2^w). Why O(2^w logN)?
To answer my own stupid question, LogN is
"Gene" <[EMAIL PROTECTED]> writes:
> 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.
Hey, I think it's cool too :-) BTW, how exactly do you generalize it?
> There
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, Tima
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
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 simp
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 i
I agree this is a different approach. But in terms of speed and space,
I wonder what is its advantages there?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send emai
While thinking about sorting chars by radix 2 I realized you can get a
very simple algorithm for putting the characters in Hamming order
rather than ascending order. This was so appealing that I coded it up
and it works very nicely.
It makes 8 passes (for w=8 bit chars) over a string to put it i
Rajiv Mathews wrote:
> @Gene
> >>Use radix sort to make it O(N W) where W is the bit-width of the
> >>characters in the string, hence O(N).
> I don't really get how a radix pass
> is going to help here either..
> Wouldn't it just order the strings, while
> we really want to order the characters i
[EMAIL PROTECTED] writes:
> So this is no better than just having an array of the counts per
> character, in terms of space and worse in terms of speed. :-/
Actually, what was I thinking, the radix approach would be better,
spacewise. In terms of space it would require O(w) space where w is
the
I should clarify my post with that on each next step you partition the
partitions.
However, this means that extra space is not zero. Partitioning
positions (at least one per bit) need to be stored. So this is no
better than just having an array of the counts per character, in terms
of space and
With the prime number approach you would need to somehow facilitate
large numbers. Also, you need to store those primes which would take
a lot of space, although admittedly you only need to take that space
once. In addition, multiplication is a much heavier opperation than
increment.
BiGYaN's a
How about the prime number approach I mentioned above. Any comments?On 4/11/06, Dhyanesh <[EMAIL PROTECTED]
> wrote:I also particularly dont like radix sort. Because it is kind of a
hack. It is not a comparison based sort. It will work with charactersas you have here. But what if you have not two s
I also particularly dont like radix sort. Because it is kind of a
hack. It is not a comparison based sort. It will work with characters
as you have here. But what if you have not two strings of characters,
but two arrays of "objects" which you can only "compare". You would
not be able to apply rad
Assuming that you cannot have any letter repeated more than 15 times.
Create a struct of 26, 4 bit bitfields. This is going to take 26x4 bits
or 13 bytes of memory.
Use this structure to store the character count of each character of
the first string.
Now proceed to the second string and for ea
Talking about radix sorting, my experience is that many job
interviewers (who are coders/developer themselvef) do not like it. Each
time when I mentioned it, they usually did not get happy with it.
What could be the reason? Any bad things in practical for radix
sorting?
--~--~-~--~~
Wrong.
Say, A is "abcd", twice of it is C "abcdabcd"
B is "bdca", B should be the premutation of A, but not a substring of
C.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this
i think we just construct a string C that repeate string A twice, for
example, string A is 'abcd', and string C is 'abcdabcd', then check
whether string B is a substring of string C.
by the way, the string C can be saved by utilizing string A and modular
function, for example, the char at positio
I had written..
>>So, using a sort the complexity really is
>>O(2n log 2), Isn't it?
Oh yeah..
That's terribly bad logic!
@Gene
>>Use radix sort to make it O(N W) where W is the bit-width of the
>>characters in the string, hence O(N).
I don't really get how a radix pass
is going to help here eith
Just of the top of my head.
You're dealing with *2* strings here.
So the *naive* method you quoted wont be that
bad.
Use a sort. The basic operation here being
string compare, which takes up O(n) time
NOTE 'n' is the length of the strings.
So, using a sort the complexity really is
O(2n log 2), Isn
Kevin wrote:
> Given two strings A and B, how to quickly check whether they are
> permutation or not?
> For example, "abcd" and "bcda" are permutation: same chars, just
> different order.
>
> Using hash: hash A and check B will use time O(N), at the cost of extra
> N space. How about do not use t
OK OK! Use the modulus operator then. Assign prime numbers mod p where p is a distinct large prime to characters and multiply.On 4/10/06, Kevin <
[EMAIL PROTECTED]> wrote:But multiply prime numbers will run out of range of integer quickly (as
I remember multiply the first 10-20 prime will get a too
But multiply prime numbers will run out of range of integer quickly (as
I remember multiply the first 10-20 prime will get a too large number
to fit into an integer).
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
How about this?Assign a prime number to each of the the characters. Multiply each of the numbers in each string and compare the product. If they are the same then it is a permutation.Cheers,Nat
On 4/10/06, Kevin <[EMAIL PROTECTED]> wrote:
But the problem is:there are much more than 26 possible char
But the problem is:
there are much more than 26 possible characters in a string, even ASCII
have 100+ characters I think, not to mention those unicode, those which
use 2 or even more bytes as a character. So the Count[] will be too
large to be practical useful.
--~--~-~--~~--
HI,
how do you intend to use hash ( as in which hash function) to check if
the hash keys generated for both A and B are equal.
Thanks,
Shishir
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group
Something on the lines of counting sort will do. Make an array
Count[26] where Count[1] will have the number of a's etc. While reading
string A, keep note of the count of the characters in Count and while
reading B, just check if the same number of characters occur.
--~--~-~--~~-
31 matches
Mail list logo
