3 Replies Latest reply on Nov 12, 2009 3:35 PM by 843853

    Unique Number Generation


      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?

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


          (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:
              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 
              we have more more and bigger members than enough.