Generate a unique number out of the combination of 'n' different numbers?

Question

To clarify, as input I have 'n' (n1, n2, n3,...) numbers (integers) such as each number is unique within this set.

I would like to generate a number out of this set (lets call the generated number big 'N') that is also unique, and that allows me to verify that a number 'n1' belongs to the set 'n' just by using 'N'.

is that possible?

Edit:

Thanks for the answers guys, I am looking into them atm. For those requesting an example, here is a simple one:

imagine i have those paths (bi-directional graph) with a random unique value (let's call it identifier):

P1 (N1): A----1----B----2----C----3----D

P2 (N2): A----4----E----5----D

So I want to get the full path (unique path, not all paths) from A knowing N1 and this path as a result should be P1. Mind you that 1,2,...are just unique numbers in this graph, not weights or distances, I just use them for my heuristic.

Answer 1

If you are dealing with small numbers, no problem. You are doing the same thing with digits every time you compose a number: a digit is a number from 0 to 9 and a full number is a combination of them that:

• is itself a number
• is unique for given digits
• allows you to easily verify if a digit is inside

The gotcha is that the numbers must have an upper limit, like 10 is for digits. Let's say 1000 here for simplicity, the similar composed number could be:

n1*1000^k + n2*1000^(k-1) + n3*1000^(k-2) ... + nk*1000^(0)

So if you have numbers 33, 44 and 27 you will get:

33*1000000 + 44*1000 + 27, and that is number N: 33044027

Of course you can do the same with bigger limits, and binary like 256,1024 or 65535, but it grows big fast.

A better idea, if possible is to convert it into a string (a string is still a number!) with some separator (a number in base 11, that is 10 normal digits + 1 separator digit). This is more flexible as there are no upper limits. Imagine to use digits 0-9 + a separator digit 'a'. You can obtain number 33a44a27 in base 11. By translating this to base 10 or base 16 you can get an ordinary computer number (65451833 if I got it right). Then converting 65451833 to undecimal (base11) 33a44a27, and splitting by digit 'a' you can get the original numbers back to test.

EDIT: A VARIABLE BASE NUMBER?

Of course this would work better digitally in base 17 (16 digits+separator). But I suspect there are more optimal ways, for example if the numbers are unique in the path, the more numbers you add, the less are remaining, the shorter the base could shrink. Can you imagine a number in which the first digit is in base 20, the second in base 19, the third in base 18, and so on? Can this be done? Meh?

In this variating base world (in a 10 nodes graph), path n0-n1-n2-n3-n4-n5-n6-n7-n8-n9 would be

n0*10^0 + (n1*9^1)+(offset:1) + n2*8^2+(offset:18) + n3*7^3+(offset:170)+...

offset1: 10-9=1 offset2: 9*9^1-1*8^2+1=81-64+1=18 offset3: 8*8^2-1*7^3+1=343-512+1=170

If I got it right, in this fiddle: http://jsfiddle.net/Hx5Aq/ the biggest number path would be: 102411

var path="9-8-7-6-5-4-3-2-1-0"; // biggest number

o2=(Math.pow(10,1)-Math.pow(9,1)+1); // offsets so digits do not overlap
o3=(Math.pow(9,2)-Math.pow(8,2)+1);
o4=(Math.pow(8,3)-Math.pow(7,3)+1);
o5=(Math.pow(7,4)-Math.pow(6,4)+1);
o6=(Math.pow(6,5)-Math.pow(5,5)+1);
o7=(Math.pow(5,6)-Math.pow(4,6)+1);
o8=(Math.pow(4,7)-Math.pow(3,7)+1);
o9=(Math.pow(3,8)-Math.pow(2,8)+1);
o10=(Math.pow(2,9)-Math.pow(1,9)+1);
o11=(Math.pow(1,10)-Math.pow(0,10)+1);

var n=path.split("-");

var res;

res=
    n[9]*Math.pow(10,0) +
    n[8]*Math.pow(9,1) + o2 +
    n[7]*Math.pow(8,2) + o3 +
    n[6]*Math.pow(7,3) + o4 +
    n[5]*Math.pow(6,4) + o5 +
    n[4]*Math.pow(5,5) + o6 +
    n[3]*Math.pow(4,6) + o7 +
    n[2]*Math.pow(3,7) + o8 +
    n[1]*Math.pow(2,8) + o9 +
    n[0]*Math.pow(1,9) + o10;

alert(res);

So N<=102411 would represent any path of ten nodes? Just a trial. You have to find a way of naming them, for instance if they are 1,2,3,4,5,6... and you use 5 you will have to compact the remaining 1,2,3,4,6->5,7->6... => 1,2,3,4,5,6... (that is revertable and unique if you start from the first)

Answer 2

Theoretically, yes it is.

By defining p_i as the i'th prime number, you can generate N=p_(n1)*p_(n2)*..... Now, all you have to do is to check if N%p_(n) == 0 or not.

However, note that N will grow to huge numbers very fast, so I am not sure this is a very practical solution.

One very practical probabilistic solution is using bloom filters. Note that bloom filters is a set of bits, that can be translated easily to any number N.
Bloom filters have no false negatives (if you said a number is not in the set, it really isn't), but do suffer from false positives with an expected given probability (that is dependent on the size of the sets, number of functions used and number of bits used).

As a side note, to get a result that is 100% accurate, you are going to need at the very least 2^k bits (where k is the range of the elements) to represent the number N by looking at this number as a bitset, where each bit indicates existence or non-existence of a number in the set. You can show that there is no 100% accurate solution that uses less bits (peigeon hole principle). Note that for integers for example with 32 bits, it means you are going to need N with 2^32 bits, which is unpractical.