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

    Unique Number Generation

    843853
      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
          (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
            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
              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.