配列を1次元につぶす - かに

配列を1次元につぶす

グリッド

$ H\times Wのグリッドのマス$ (i,j)（0-indexed）は、各マスに対して$ Hi+jと番号をふることで$ 1次元として扱える。

code: grid_mask

def mask(i, j):

return H * i + j

code: grid_unmask

def unmask(x):

i, j = divmod(x, H)

return (i, j)

一般的な変換

$ i, j, kの取り得る値が

$ 0 \leq i < 2^a

$ 0 \leq j < 2^b

$ 0 \leq k < 2^cであるとき、順序組$ (i, j, k)を$ 2^{a+b+c}以下のただひとつの整数と対応付けることができる。

code: mask(i, j, k)

def mask(i, j, k):

i <<= (b + c)

j <<= c

return i ^ j ^ k

code: unmask

K = 30

mypow = 0 for _ in range(K+1)

p = 1

for k in range(K+1):

mypowk = p-1

p <<= 1

def unmask(i):

k = i & mypowc

i >>= c

j = i & mypowb

i >>= b

return (i, j, k)