Encode an array of integers into a unique int

Question

I have a fixed number of form int arrays:

[a,b,c,d,e] 

eg:

 [2,2,1,1,2] 

where a and b can be int from 0 to 2, c and d can be 0 or 1, and e can be int from 0 to 2.

Consequently, there are: 3 * 3 * 2 * 2 * 3 : 108 possible arrays of this form.

I would like to assign each of these arrays a unique integer code from 0 to 107.

I'm stuck, I was thinking about adding each number to an array, but two arrays, such as:

 [0,0,0,0,1] and [1,0,0,0,0] 

both would add to 1.

Any suggestion?

Thanks.

Answer 1

You can use np.ravel_multi_index :

 >>> np.ravel_multi_index([1, 2, 0, 1, 2], (3, 3, 2, 2, 3)) 65 

Validation:

 >>> {np.ravel_multi_index(j, (3, 3, 2, 2, 3)) for j in itertools.product(*map(range, (3,3,2,2,3)))} == set(range(np.prod((3, 3, 2, 2, 3)))) True 

Return to the other side:

 >>> np.unravel_index(65, dims=(3, 3, 2, 2, 3)) (1, 2, 0, 1, 2) 

Answer 2

This is a bit like converting numbers from a base of numbers of various sizes into a standard integer. In base 10, you can have five digits, each of which is from 0 to 9, and then you converted them into a single whole using i = a*10000 + b*1000 + c*100 + d*10 + e*1 .

Equivalently, for decimal conversion you can write i = np.dot([a, b, c, d, e], bases) , where bases = [10*10*10*10, 10*10*10, 10*10, 10, 1] .

You can do the same with your bases, except that your positions are entered by factors [3, 3, 2, 2, 3] instead of [10, 10, 10, 10, 10]. Therefore, you can set bases = [3*2*2*3, 2*2*3, 2*3, 3, 1] (= [36, 12, 6, 3, 1]), and then use i = np.dot([a, b, c, d, e], bases) . Please note that this will always give answers in the range from 0 to 107 if a, b, c, d and e fall into the ranges you specify.

To convert i back to a list of numbers, you can use something like this:

 digits = [] remainder = i for base in bases: digit, remainder = divmod(remainder, base) digits.append(digit) 

On the other hand, to keep your life simple, you are probably better off using Paul Panzer's answer, which pretty much does the same. (I never thought of an n-digit number like the coordinates of a cell in an n-dimensional grid before, but it turns out that they are mathematically equivalent. And np.ravel is an easy way to assign a serial number to each cell.)

Answer 3

Another way similar to Horner's method for polynomials:

 >>> array = [1, 2, 0, 1, 2] >>> ranges = (3, 3, 2, 2, 3) >>> reduce(lambda i, (a, r): i * r + a, zip(array, ranges), 0) 65 

It is expanded that (((0 * 3 + 1) * 3 + 2) * 2 + 0) * 2 + 1) * 3 + 2 = 65.

Answer 4

This data is small enough for you to simply list them:

 >>> L = [[a,b,c,d,e] for a in range(3) for b in range(3) for c in range(2) for d in range(2) for e in range(3)] >>> L[0] [0, 0, 0, 0, 0] >>> L[107] [2, 2, 1, 1, 2] 

If you need to go the other way (from array to integer), make a dict request for it so that you get O (1) instead of O (n):

 >>> lookup = {tuple(x): i for i, x in enumerate(L)} >>> lookup[1,1,1,1,1] 58 

Answer 5

getting the dot-product your vectors as follows:

 In [210]: a1 Out[210]: array([2, 2, 1, 1, 2]) In [211]: a2 Out[211]: array([1, 0, 1, 1, 0]) In [212]: a1.dot(np.power(10, np.arange(5,0,-1))) Out[212]: 221120 In [213]: a2.dot(np.power(10, np.arange(5,0,-1))) Out[213]: 101100 

must produce 108 unique numbers - use their indices ...

Answer 6

If the length of the array is not very long, you can first calculate the weight, and then use a simple mathematical formula to get the identifier. The code will look like this:

 #Test Case test1 = [2, 2, 1, 1, 2] test2 = [0, 2, 1, 1, 2] test3 = [0, 0, 0, 0, 2] def getUniqueID(target): #calculate out the weights first; #When Index=0; Weight[0]=1; #When Index>0; Weight[Index] = Weight[Index-1]*(The count of Possible Values for Previous Index); weight = [1, 3, 9, 18, 36] return target[0]*weight[0] + target[1]*weight[1] + target[2]*weight[2] + target[3]*weight[3] + target[4]*weight[4] print 'Test Case 1:', getUniqueID(test1) print 'Test Case 2:', getUniqueID(test2) print 'Test Case 3:', getUniqueID(test3) #Output #Test Case 1: 107 #Test Case 2: 105 #Test Case 3: 72 #[Finished in 0.335s]