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.

How to generate an unique integer number from given $21$ integers, sequence doesn't matter. Also It is NOT required to regenerate these 21 numbers from this unique number. What would be the best mathematical solution for this? These $21$ numbers would be in range $0$ to $5250021$. Please help.

Thanks, Sagar.

share|improve this question
    
So you want a unique integer from a 21-element subset of $\{0,\dots,5250021\}$? Or are the 21 integers allowed to repeat? –  Thomas Andrews Apr 9 '13 at 15:05
    
Seems that way, a unique map from $C(5250022, 21) \rightarrow \Bbb N$. I would +1 if I had any votes left. –  muzzlator Apr 9 '13 at 15:06

3 Answers 3

So, write in base 5250022?

Be $n_i, i<21$ your 21 sorted integers, and build $N=\sum_{i=0}^{21} n_i 5250022^i$.

share|improve this answer
1  
"Sequence doesn't matter." Presumably, a different order shouldn't give a different integer. –  Thomas Andrews Apr 9 '13 at 15:07
1  
then sort them before. –  Benoit Apr 9 '13 at 15:08

So you want a unique integer from a 21-element subset of $\{0,\dots,5250021\}$? There is the squashed order, which is relatively easy to calculate.

If $0\leq n_1<n_2<\dots<n_{21}\leq 5250021$ you can generate a unique integer from $0$ to $\binom{5250022}{21}-1$ by the formula:

$$\sum_{j=1}^{21} \binom{n_j}{j}$$

This is related to something called the squashed order.

If you are allowed repeating $n_i$, then let $m_i=n_j+j-1$. Then $$0\leq m_1<m_2\dots <m_{21}\leq 5250041$$ and we get a distinct number from $0$ to $\binom{5250042}{21}-1$ by computing:

$$\sum_{j=1}^{21} \binom{n_j+j-1}{j}$$

These are in some sense the best you can do, since there are $\binom{5250022}{21}$ different sets of $n_j$ in the first case and $\binom{5250042}{21}$ different sets of $n_j$ in the second case (where repetitions are allowed.)

I've actually used this technique in some computer programs, but it is very slow if you can't pre-compute all the $\binom{n}{k}$ that you'll potentially need - essentially, the base $5250022$ solution is faster if you don't mind gaps and the extra ~65 bits in your results.

(Weirdly, if you Google "squashed order" the first result that comes up is a description of the algorithm of something I wrote. That article references "Anderson, Combinatorics on Finite Sets, pp 112-119," so that might be a good place to look for more about the squashed order.

One nice thing about this index is that it doesn't change with your upper bound - if you suddenly decide to allow numbers from $0$ to $5250023$, the old indices for the other sequences remains the same.

share|improve this answer

If you have a fixed upper limit, you can just zero pad them on the left to the same length and concatenate. In this case it would be like working in base 10,000,000. Each "digit" is in the range $0,000,000$ to $9,999,999$ This does allow regenerating them and having a different output depending on the order of the input numbers.

There are many other solutions. Best is in the eye of the beholder. This one seems easy to understand.

share|improve this answer

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.