Encode array of integers into unique int

Question

I have a fixed amount of int arrays of the form:

[a,b,c,d,e]

for example:

[2,2,1,1,2]

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

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

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

I am stuck, i thought of adding each numbers in the array, but two arrays such as:

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

would both add to 1.

Any suggestion?

Thank you.

did not follow your explanation. If you have 108 arrays, and want a unique number to each, why not just add values from 0 to 127? — Alg_D, Jan 23 '18 at 22:40
I would like to know if there is a known function that can take such an array and output a unique int. So every time I put this array as an input I get the same unique output . — user2505650, Jan 23 '18 at 22:42
Can you enumerate and add integer keys to each possible combination? — Zhiya, Jan 23 '18 at 22:44
You say you "have a fixed amount of int arrays". In what data structure do you have these arrays? — Stefan Pochmann, Jan 23 '18 at 23:20

score 16 · Accepted Answer · edited Jan 24 '18 at 00:48

16

You could 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

Going back the other way:

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

edited Jan 24 '18 at 00:48

wim

338,267
99
616
750

answered Jan 23 '18 at 22:45

Paul Panzer

51,835
3
54
99

1

it's brilliant ! – MaxU - stand with Ukraine Jan 23 '18 at 22:47

Matthias Fripp · Answer 2 · 2018-01-24T21:35:34.060

This is a little like converting digits from a varying-size number base to a standard integer. In base-10, you could have five digits, each from 0 to 9, and then you would convert them to a single integer via i = a*10000 + b*1000 + c*100 + d*10 + e*1.

Equivalently, for the decimal conversion, you could 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 thing with your bases, except that your positions introduce multipliers of [3, 3, 2, 2, 3] instead of [10, 10, 10, 10, 10]. So you could 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). Note that this will always give answers in the range of 0 to 107 if a, b, c, d, and e fall in the ranges you specified.

To convert i back into a list of digits, you could 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 thing. (I never thought of an n-digit number as the coordinates of a cell in an n-dimensional grid before, but it turns out they're mathematically equivalent. And np.ravel is an easy way to assign a serial number to each cell.)

This is implementing `np.ravel_multi_index` and `np.unravel_index` from first principals. Helpfully demonstrated, and a good use of `divmod` +1 — wim, Jan 24 '18 at 00:51

score 3 · Answer 3 · answered Jan 23 '18 at 23:29

Just 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

Unrolled that's ((((0 * 3 + 1) * 3 + 2) * 2 + 0) * 2 + 1) * 3 + 2 = 65.

score 1 · Answer 4 · answered Jan 23 '18 at 22:43

This data is small enough that you may simply enumerate 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 the array to the integer) make a lookup dict for it so that you will get O(1) instead of O(n):

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

score 0 · Answer 5 · answered Jan 23 '18 at 22:42

getting dot-product of your vectors as following:

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

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

Sphinx · Answer 6 · 2018-01-24T17:30:13.793

If the array lenght is not very huge, you can calculate out the weight first, then use simple math formula to get the ID. The code will be like:

#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]

thank you, where do those weights numbers come from? – user2505650 Jan 23 '18 at 23:15 — user2505650, Jan 23 '18 at 23:15

Encode array of integers into unique int

6 Answers6

Linked