なおしのこれまで、これから

学んだこと・感じたこと・やりたいこと

多次元配列を1次元配列に変換する計算

始めに

過去記事の内容で3次元配列を1次元配列にする解説が少しわかりにくいとなり、補足記事を書こうと思います。

shitakami.hatenablog.com

2次元配列を1次元配列にする

まずは2次元配列から1次元配列に変換することから始めます。

例として高さ3、幅5の2次配列があるとします。 横方向がx軸、縦方向がy軸として要素は0から始まるものとします。

下の図は各マス目をyとxで表したものです。

f:id:vxd-naoshi-19961205-maro:20201113190517p:plain


上の図から、(y, x) = (2, 1)とすれば上から3番目の左から2番目の要素を表します。



この表をyとxで表しましたが、次はx'だけで表したいと思います。要素の数え方は一番上の左から右方向へ数えて、一番右まで数えきったら下に移動して同様に左から右へ数えていきます。

下の図は各マス目をx'で表したものです。

f:id:vxd-naoshi-19961205-maro:20201113192345p:plain



ではここから(y, x)を使ってx'を求める計算をしていこうと思います。

x'の表からわかることをいくつか列挙していきます。

あるマスから右隣に移動するとx' + 1となり、下に移動するとx' + 5となります。

f:id:vxd-naoshi-19961205-maro:20201113194915p:plain


よってxが1増えるとx'+1となり、yが1増えるとx'+5となるので  x' = 5y + xとなります。

例えば、(y, x) = (2, 3)だった場合は x' = 5 \times 2 + 3= 13で(y, x)の表の位置とx'の表の位置が一致していることがわかります。



ここで、x' = 5y + xの5yの部分に注目すると5が幅の大きさに一致していることがわかります。

よって、高さheight、幅widthの2次元配列(y, x)を1次元配列x'にする計算は次のようになります。


x' = y \times width + x



3次元配列を1次元配列にする

例として高さ3、幅5、奥行3の3次元配列があるとします。

下の表(z, y, x)は手前がz=0で一つ奥の表に行くごとにzが増えていきます。

f:id:vxd-naoshi-19961205-maro:20201113225446p:plain


同様にこれもx'の表に直していきます。 1つの表が埋まれば次の表に移って数え続けます。

f:id:vxd-naoshi-19961205-maro:20201113230344p:plain



ここから(z, y, x)を使ってx'を求める計算を考えていきます。 xとyについては2次元配列と同様なので省きます。

2次元配列の表が次のものに移るとx'の値はx'+15されていることがわかります。

f:id:vxd-naoshi-19961205-maro:20201113230903p:plain



よって、zが1増えるとx'は15増えるので x' = 15z + 5y + xとなります。

例えば(z, y, x) = (2, 0, 3)とすると x' = 15 \times 2 + 5 \times 0 + 3 = 33となり(z, y, x)の表とx'の表の位置が一致していることが確かめられます。


ここで15zの15に注目すると高さ×幅=3×5=15と一致していることがわかります。

よって、奥行depth、高さheight、幅widthとすると3次元配列(z, y, x)を1次元配列x'に変換する数式は次のようになります。


x' = z(height \times width) + y \times width +x



多次元配列を1次元配列にする

ここまでこれば何となく法則性がわかってきたと思います。

例えば5次元配列があったとしてそれぞれの次元の大きさが(s_0, s_1, s_2, s_3, s_4)とすると5次元配列(i_0, i_1, i_2, i_3, i_4)を1次元配列i'に変換する数式は次のようになります。


i' = i_0(s_1 \times s_2 \times s_3 \times s_4) + i_1(s_2 \times s_3 \times s_4) + i_2(s_3 \times s_4) + i_3 \times s_4 + i_4



この数式を一般化したいと思います。(数学詳しくないので正しくないかもしれません!)

n次元配列(i_0, i_1, i_2, . . . i_n)がありそれぞれの次元の大きさを(s_0, s_1, s_2, . . . . s_n)とするとn次元配列を1次元配列i'にすると次のような数式になります。


i' = i_0 \prod_{x=1}^{N} s_x + i_1 \prod_{x=2}^{N} s_x + . . . . i_{n-1} \times s_n + i_n



すべての次元の大きさが同じ場合はn進数になる

ここでn次元配列のすべての次元の大きさがXで同じ場合を考えたいと思います。

このときn次元配列(i_0, i_1, i_2, . . . i_n)を1次元配列i'にすると次にようになります。


i' = i_0 X^{n - 1} + i_1 X^{n - 2} + . . . . + i_{n - 2} X^2 + i_{n - 1} X + i_n


これは実はn進数を10進数に変換する計算と一致します。 こう覚えておくと何となく便利かなと思ってます。

参考:【基本】n進法への変換(整数) | なかけんの数学ノート



最後に

少しだけ雑談しますと、前のブログの解説について後輩と友達に相談して結構議論になりました。ある人はこの内容が積分だと解釈しある人は行列と解釈し、話していて様々な見方が出来る内容なのかなと感じました。

私個人としてはこの内容をn進数と見て考えていまして、そういう風に今回の内容をまとめました。

少し競技プログラミングっぽいような感じの内容かもしれませんが、ときによってはゲームプログラミングに役立つかもしれません。