Given a set of different integers A, each integer is in range from 1
to 7500. It may be assumed that the set size won't be more than 50
(ie: |A|<=50).

I need a one-to-one function f that takes set A and returns a unique
double number for given set A: (f: {..} --> R)

So for any two different sets A!=B function output will be different 
f(A)!=f(B) (!= stand for not equal). Of course, since A is a set, the
order of integers in it doesn't matter, so A={1,2,3} identical to
B={3,1,2} and in this case I should get f(A)=f(B).

I'm sure there are a lot of functions that do the job, but only
functions which use primitive operators such as +,-,*,/ will be
preffered.

What I have thought of, is the following function, but I'm not sure
it's one to one, since I haven't found a contradicting example. Anyway
this function is VERY slow, since it uses power operator ^:
Suppose A={X1,X2,..,Xn} where each 1<=Xi<=7500
Let n be number of elements in A: n=|A|
f(A)=(x1)^(0.n) + (x2)^(0.n) + ... + (xn)^(0.n)   

So for example, if |A|=5 then 0.n=0.5 and if given a set  A={2, 3004,
4443} then |A|=3 and f(A)=2^0.3 + 3004^0.3 + 4443^0.3=24.70499967.

Of course, it is obvious that 0.n0=.n, but knowing the high bound on A
size, it is always possible to work around this. So if |A|<=50 then we
could transform numbers like 0.n0 to 0.nnn. (So for example, if |A|=3
then 0.n=0.3 but if |A|=30 then 0.n=0.333).

---

Request for Question Clarification by efn-ga on 18 Apr 2004 14:21 PDT

What do you mean by "double number"?  Are you referring to a 64-bit
double-precision floating-point number as used in a computer?

---

Request for Question Clarification by mathtalk-ga on 18 Apr 2004 21:56 PDT

If you were working with exact arithmetic, then continued fractions
would be a natural approach for this sort of thing.

However in "double" precision you would presumably not have enough
possible results to permit "a unique double number" to be returned for
each set A.

Consider that there are 7500 subsets of size 1, 7500*7499/2 subsets of
size 2, and so on, up to 7500!/(50!7450!) subsets of size 50.

Just to count the last category of subsets would require 430 bit
numbers.  Most floating point implementations of "double precision"
only use 64 bits, and thus we cannot avoid "collisions" in which the
same result is obtained for more than one input subset.

regards, mathtalk-ga

alex130-ga,

I guess you are looking for a method to compare two arrays of 
integers. If so, try this "function". It will eliminate some 
collisions if you map a large ammount of data (your array) to 
a very small one (a single number here). Cryptographic hash 
functions (MD5) have the same problem, and they solve it with 
some complex "cryptograhic operations". However, you will never 
get a collision free one-to-one function this way!!

Here we go...

A = (a,b,c,d), n = 4

f(A) = n + ((xor(a,b,c,d) / ((a+b+c+d)/n)) / 10000)

example: 

A = 10 50 733 1345 ; f(A) = 4 + ((1956) / (2138/4)) / 10000 = 4.24905
B = 733 10 1345 50 ; f(B) = 4 + ((1956) / (2138/4)) / 10000 = 4.24905

==> f(A) == f(B) ==> A is identical to B

Explanation: 

"n + " helps us to recognize arrays with different lenghts.

XOR(a,b,c,d) will give the same value, regardless of the order. 
However, XOR will fail to distinguish between (6,1,9,4) and (4,6,8,0). 
So, we need some more math. 

((a+b+c+d)/n)) will caluclate the mean value. As we need to have the
same array length (see "n +"), this will help us with the problem above.

"/ 10000" will "shift" the mean value below 0. Remember: we asume that 
the value of the array members is <= 7500.

By double number I indeed mean a 64-bit
double-precision floating-point number as used in a computer, like C++
or Java variable of type double. I'm going to implement this function
in Java or C++.

Hi, you solution looks pretty good, buy are you sure that 64 bit
precision of double variable (in C++ or Java) will be enough to avoid
collisions?

As quizmaster_1-ga pointed out, the hash function is not "collision free".

However if you only plan to apply the method a moderate number of
times, the chances of a collision may be negligibly small if a very
sophisticated hash function is used.

--mathtalk-ga

One other way that gives one-to-one function is use 7501 bits.
Mark appropriate bits corresponding to elements ( integers) of set A or B.
The resulting "number" ,call it n, ( which is quite big) is your f(A) or f(B).
Note that you need log(n) bits to store n itself. so you can store
log(n) as probably a double precision.

Hi, atag_355113-ga:

I think the point you are getting at here is that with 7500 bits you
could describe _every_ subset of 7500 numbers.  Of course alex130-ga
has only requested a mapping that could handle subsets of up to size
50.

With that restriction one would need at most 436 bits to enumerate all
the possibilities, but naturally this is still much larger than the
number of bits used to represent a (floating-point) double.

regards, mathtalk-ga