3 Replies Latest reply: Nov 12, 2009 9:35 AM by 843853

# Unique Number Generation

Hi,

Suppose I have a list of numbers, say (a,b....n) i want to generate a unique number say u so that no other list, say (a1,b1... n1) will not give a number u1 and u!=u1 if (a,b...n)!=(a1,b1...n1)

More over (a,b,...n) is same list as (b,a...n), so they should both generate u, ie order does not matter.

Any one has any idea?

What i came up with is (a+b+...n)+(a*b*...*n), can this fail in any time?

Regards,
Jishnu
• ###### 1. Re: Unique Number Generation
(3,2,1) & (6)

or

(0, 5,10) & (0,15)

Edited by: sabre150 on Nov 11, 2009 9:59 AM
• ###### 2. Re: Unique Number Generation
Well obviously you need more restrictions than that since sigma(i=0...2^32, 2 ^32^ choose i) is much larger than the value of a long or an int. In other words, there are more combinations of arbitrary lists of unique integers than there are values in an int or a long. You can't guarantee uniqueness. Period. You'd have to use a BigInteger at the very least.

Now, if you place some restrictions (like the max value of M), than maybe we have somewhere we can start.

If you're looking for close-to-unique, I'd sort the list and pass it through Arrays.hashCode(int[]).
• ###### 3. Re: Unique Number Generation
This is some mathematics, where natural numbers can be arbitrary big.

We are talking about natural numbers.
So we have ordered our sequence of natural numbers:
``````a(1)<=...<=a(n)
Adding i to the i-th member we have a strictly increasing series.
We work with strictly increasing series.

So we compute a(1) ^ 2 + a(2)  ^4 + a(3) ^ 8 + ....

But we need a lemma: if a<=b natural numbers,
then a,b can be gained (computed) back from f(a,b)=a+b^2.
Indeed, obviously
b^2 <= f(a,b) = a + b^2 <= b + b^2 < 1 + 2*b + b^2 = (b+1) ^2
So (b+1)^2 is the smallest square number which is bigger than f(a,b),
so we can compute back b and thus a.

Now if we compute the above expression up to the member a(k), we obtain
f(k) = a(1) ^ 2 + a(2)  ^4 + a(3) ^ 8 + ....+ a(k) ^ (2^k)
The member whose square is to be added to come to f(k+1) is a(k+1)^(2^k).
We can apply our lemma, if f(k) is not greater than the above number.

Let a(k) be A, then all a(i) up to it will be be <=  A,
f(k)  <= A + A^2 + A^4 + ... + A^(2^k)
Even the right hand side expression is <= a(k+1) ^ (2^k) ,
because a(k+1) must be at least (A+1), and if we apply the binomial expansion to
(A+1)^(2^k)
we have more more and bigger members than enough.``````