Help us understand the problem. What is going on with this article?

Pythonで表現する座標あれこれ

はじめに

paizaやAtCoderの問題で座標はよく出てきますし、将棋や囲碁などのボードゲームを作成するときや、エイトクイーン問題を解くときは必ず座標を使います。
この記事では、座標の多様な表現を紹介します。

よくある座標

以下の座標を二つのデータ構造で表現します。

1 2 3
1 a b c
2 d e f

ここでは横に並ぶ番号(列番号)をx, 縦に並ぶ番号(行番号)をyとします。

伝統的二次元配列

>> point = [['a', 'b', 'c'], ['d', 'e', 'f']]
>> point[0][0]
'a'
>> point[1][1]
'e'

メリット

  • forループが簡単。
goal = {'a', 'c', 'f'}
for row in point:
    for cell in row:
        if cell in goal:
            print(cell)
# a
# c
# f

デメリット

  • 要素へのアクセス方法が直感的でない。

((縦, 横)の順でアクセスするのは案外普通なのですが)
x と y を使う場合は(x, y)、つまり(横, 縦)と見たいです。
そういう時はこのデータ構造ではプログラミング中、少し頭を使います。
多少見栄えをよくする方法はあります。

point = [['a', 'b', 'c'], ['d', 'e', 'f']]

point = [['a', 'b', 'c'],
         ['d', 'e', 'f']]

行ごとに改行すると多少見やすいでしょうか。
しかし、縦番号をy、横番号をx とした場合、
アクセス方法はpoint[y-1][x-1]となります。

print(point[1-1][3-1])
# 'c'

x → y という記述では無くなり、さらに-1する羽目になります。
少しめんどくさいです。


上記の例の解釈はいわば、行の配列です。
少し考えると、データを列の配列と解釈することも可能なことがわかります。

point = [['a', 'd'],
         ['b', 'e'],
         ['c', 'f']]

コーディング上ではわかりづらいですが、アクセスは
point[x-1][y-1]となり、少し直感的になりました。

point[3-1][1-1]
# 'c'

一般的なのはどちらか

行の配列、列の配列、それぞれに有用性がありますが、
一般的なのは、行の配列だと思います。

point = [['a', 'b', 'c'],
         ['d', 'e', 'f']]

Excelでの集計や、データベース操作のGUIクライアントアプリは行を下に向かって並べるように表示をしていることが多いです。

例: 行の配列

id name age
1 python_man 20
2 python_girl 18

データの形式をみたときに馴染みやすいのは行の配列だということは、多分多くの人が感じることだと思います。ですので(縦, 横)の順に見るのが案外普通だったりします。
伝統的二次元配列はとにかくシンプルで、記述が簡単なやり方です。x, yの場合の要素のアクセスは少し頭を使いますが。

組(タプル)に値を対応させる辞書型

オススメの方法です。

1 2 3
1 a b c
2 d e f

eの場所はどのように表しますか。
横番号をx, 縦番号をy として、
(x, y) → 文字 というふうに考えてみてください。

...

(2, 2) → e

になるのかなと思います。
他のも表してみましょう。

(1, 1) → a
(3, 2) → f

はい、簡単です。
これが馴染むのであれば、これをそのまま辞書にしてしまいましょう。

>> point = {(1, 1): 'a', (2, 1): 'b', (3, 1): 'c',
            (1, 2): 'd', (2, 2): 'e', (3, 2): 'f'}

ええ〜〜〜〜 or なるほど〜〜〜〜
というのが予想される反応です。私が初めてこの記述に出会った時の反応は(ええ〜〜なにこれキモ。ありえん。絶対間違ってるべ) でした。
ところで、アクセスはどうなるでしょう。

>> point[3, 2]
'f'

驚くほど直感的です。
それでもやはり、
{(1, 1): 'a', (1, 2): 'b', ...} 書くのは面倒です。

そんな時は二次元配列を辞書型に変換する関数を定義すれば良いのです。

def to_matrix_dict(ary):
    y_range = range(1, len(ary) + 1)
    x_range = range(1, len(ary[0] + 1)
    return {(x, y): ary[y-1][x-1] for y in y_range for x in x_range}

変換してアクセスしてみます。

>> point = [['a', 'b', 'c'],
            ['d', 'e', 'f']]
>> mat = to_matrix_dict(point)
>> mat[2, 2]
'e'
>> mat[1, 1]
'a'
>> mat[3, 2]
'f'

メリット

  • アクセス方法が直感的。
  • 実は行列の定義にそっくりで数学っぽい。

デメリット

  • forループではrangeを使わないと順序性を保てない。
  • 馴染みづらい(?)

少し特殊な座標

以下の座標を考えてみましょう。

1 2 3 4 5 6 7 8
1 * *
2 * *
3 * *
4 * *

座標に何かがあるというパターンです。
つまり、

  • (1, 1) → なし
  • (2, 1) → なし

...

  • (7, 1) → あり
  • (8, 1) → あり

...

というパターン。
さらにこの座標は横番号xに対応する縦番号yが一つだけ定まります。
(yからxは複数あります)
数学的に言うなら、X → Y の写像が全射であり単射でないパターンです。

このような座標が使われるシーンは例えば離散的な時間軸に沿って何かの状態が表されているときなどです。(例: 月ごとの売上)

他にも将棋の自陣の歩の位置などもこのような座標で表現できます。

こういう場合に役に立つ表現があります。

xからyへの対応

伝統的な二次元配列の表現では以下のようになりそうです。

ありがちな表現は、存在しないとき 0 とし、存在するとき 1 とする方法。

point = [[0, 0, 0, 0, 0, 0, 1, 1],
         [0, 0, 0, 0, 1, 1, 0, 0],
         [0, 0, 1, 1, 0, 0, 0, 0],
         [1, 1, 0, 0, 0, 0, 0, 0]]

悪くはないですが、先ほども述べたように
上の表は横番号に対応する縦番号が一つだけなので、
次のように一次元配列で表すことが可能です。

point = [4, 4, 3, 3, 2, 2, 1, 1]

縦番号をそのまま配列に入れてしまいます。
縦番号が一つだけ定まる場合、かつ、存在するかどうかだけを確認したい場合は効率的です。
ただ、このままだと添字は微妙で横番号のときだけ -1 する必要があります(point[y][x-1])

ここは諦めて縦番号もあらかじめ-1しておきましょう。

>> point = [3, 3, 2, 2, 1, 1, 0, 0]
>> point[1 - 1] == 4 - 1
True

辞書型を使えば、-1する必要は無くなります。

>> point_dict = {1: 4, 2: 4, 3: 3, 4: 3, 5: 2, 6: 2, 7: 1, 8: 1}
>> point_dict[1] == 4
True

辞書型を使いたい場合、zipdict簡単に生成できます。

>> point = [4, 4, 3, 3, 2, 2, 1, 1]
>> x_range = range(1, len(point)+1)
>> point_dict = dict(zip(x_range, point))
>> point_dict[3] == 3
True

おわりに

今のところ私が出会った座標の表現は以上になります。
それぞれに有用性があると思いますので、場面で使い分けるのが良いと思います。

他にもこんな表現があるという方は是非コメントで教えてください。

おまけ: それぞれの表現の数学的解釈

伝統的二次元配列

一般的な平面座標。

組(タプル)から値への対応

行列の定義にそっくり。行列の厳密な定義(Wikipedia)
行列を集合を使って定義するとしたら以下のようになります。

行数を m、 列数を n とするとき、
R = {1, ..., m} と C = {1, ..., n} の直積集合 R×C から、成分の属する体Fへの写像となります。

R×C \rightarrow F

添字をi, j とすると成分xへの対応は以下のようになります。

(i, j) \mapsto x

これはまさに紹介した通りの辞書型の形です。

xからyへの対応

中学で習う一次関数に近いです。

$$y = 2x$$という一次関数を表現したいとき、
要素番号をそのままxの値として、要素をyの値としたら

y_set = [0, 2, 4, 6, 8, 10, 12]

となります。

またまた余談ですが、関数はまたの名を写像(map)と言いますが
高階関数のmapはまさにこれを示します。
コーティング上わかりやすくするために
f(x) = 2x と定義します。

>> def f(x): return 2 * x
>> x_set = [0, 1, 2, 3, 4, 5, 6]
>> y_set = list(map(f, x_set))
>> y_set
[0, 2, 4, 6, 8, 10, 12]

Pythonは結構数学的記述に寄り添っているため、Pythonを勉強しながら数学を勉強、もしくは数学を勉強しながらPythonを勉強すると相互に理解が深まって楽しいと思います。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away