This content has been marked as final. Show 3 replies
(3,2,1) & (6)
(0, 5,10) & (0,15)
Edited by: sabre150 on Nov 11, 2009 9:59 AM
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).
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.