Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I came across this question while thinking about a CS problem:

Given a set $S = [a,b]$ , and a string $x \in S^{n}, x = r_1r_2 \cdots r_n$, under what conditions is $H(x) = r_1 * r_2 * \cdots * r_n$ a bijection with $S^{n}$?

CS Background: i.e I have a string of length $n$, with ASCII character codes from $a$ to $b$, and I want to map all permutations of a string to the same place in a hash table, any other string to a different place. I was thinking of when multiplying the ASCII codes out as a hash function would work.

My idea was that if I have a string of two numbers, $x.y$, then $x*y$ will be unique as long as $\frac{x}{k_1}$ and $(x*k_1)$ arent in $S$, and $\frac{y}{k_2}$ and $(y*k_2)$ aren't in $S$, where $k_1$,$k_2$ are the smallest prime factors of $x$ and $y$ respectively.

But then I ran a program to test this with $a=51$, $b=100$. This should give me a bijection by the logic above, since the min element is 51 and 51*2=101 (2 is smallest possible prime factor) is not in the set, but $4104 = 54*76 = 57 * 52$ is a counter-example.

share|improve this question
    
How interested are you in the specific problem you have asked, versus whatever problem you are actually trying to solve? Anyways, except for some extremely specialized applications (e.g. tables of keywords for compilers) hash functions are pretty much never bijective, especially once you put realistic constraints on them (e.g. indexing into a table of length less than the set of all possible keys). –  Hurkyl Mar 3 '13 at 10:13
    
@Hurkyl I'm asking more out of curiosity rather than any practical application at this point. So I'm just interested in the specific problem. –  Ankit Soni Mar 3 '13 at 10:37
    
It doesn't even have to be practical; e.g. your exposition suggests it's plausible you're more interested in the problem of how to write hash functions that give the same value to all permutations of the input. –  Hurkyl Mar 3 '13 at 13:31
add comment

1 Answer

Just fix a different prime number $p(r)$ for each $r\in [a,b]$. Then, the function $$H(\text{"}r_1\ldots r_n\text{"}):=p(r_1)\cdot\ldots\cdot p(r_n)$$ is of the required property. (It is also enough that $p(r)$'s are pairwise coprime.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.