This discussion is archived
3 Replies Latest reply: Nov 12, 2009 7:35 AM by 843853 RSS

Unique Number Generation

843853 Newbie
Currently Being Moderated
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
    843853 Newbie
    Currently Being Moderated
    (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
    843853 Newbie
    Currently Being Moderated
    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
    843853 Newbie
    Currently Being Moderated
    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.