TIM Labs

Python で Android の指リストパターンを数え上げる (その2)

えっ。Python での実装はもうあるじゃん...。まったくもって今更何を言いだすのか。 "There's Only One Way To Do It" を掲げる Python にもかかわらず「その2」などとは。

とはいうものの、いかに Python といえども、やはりやり方をひとつに絞ることはできはしない。 比較的 Python らしい、ジェネレータを使用したやりかたは既に示されている。 そこで本記事では、もうひとつのやり方として元々の Haskell版 のクローンを Python で実装してみようと思う。

なお本記事では Python 3.2 を使用する。

何? まだ Python 2 系を使ってる? もう古いので早急に乗り換えを検討されるとよろしい。

Python で書いてみる

さて、目指すは Haskell 版のクローンである。同じく blocklist を定義しよう。

blocklist = {
    1: {2: 3, 4: 7, 5: 9},
    2: {5: 8},
    3: {2: 1, 5: 7, 6: 9},
    4: {5: 6},
    5: {},
    6: {5: 4},
    7: {4: 1, 5: 3, 8: 9},
    8: {5: 2},
    9: {5: 1, 6: 3, 8: 7},
}

こういった用途には Python では dict が担当してくれる。邪魔するボタンが key で、邪魔されるボタンが value だ。 Haskell ではリストを用いているために lookup には線形時間がかかるが、Python なら対数時間探索が期待できる。 (ただし対数時間は二分木での実装の場合。実際の内部実装はハッシュテーブルのようなので、定数時間かもしれない。)

もっとも今回の場合はたかだか 3 要素しかないので、オーバーヘッドにより Python の方が若干不利だと予想されるが、 要素数が増えるほど Python の方が有利になっていくはずだ。

その辺さておき、Python の interactive shell を起動してコード片をコピー&ペーストしよう。 複数行あっても、余分な空行がなければ正しく認識してくれるので便利だ。

>>> blocklist[1]
{2: 3, 4: 7, 5: 9}
>>> blocklist[1][2]
3

二回目は「今 1 のボタンに居るとき、2 のボタンが未選択なら、3 のボタンへは進めない」を意味する。 この添え字によるアクセスは構文がシンプルで大変良いのだが、

>>> blocklist[1][6]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 6

key が見つからないとエラーになって面倒だ。そんな場合は get を用いる。第二引数には key が見つからなかった場合のデフォルト値を指定できる。

>>> blocklist.get(1, {}).get(6, 0)
0

デフォルトを指定しなければ None になる。

さて、このことを未選択なボタン全てに対して調べていけば、邪魔されるボタンの一覧が手に入るのだった。 Haskell では map 関数を使用した。Python にも同等の map 関数があるが、ジェネレータ式が map の代わりをしてくれるのでそちらを使うことにしよう。

>>> list(blocklist.get(1, {}).get(i) for i in [2,3,4,5,6,7,8,9])
[3, None, 7, 9, None, None, None, None]

これを未選択のボタンから「引け」ばいいのだが、そんなときは set の出番で、こういう用途に特化されたコンテナだ。

>>> set([1,2,3,4]) - set([2,3])
{1, 4}

簡単だね。

>>> set([2,3,4,5,6,7,8,9]) - set(blocklist.get(1, {}).get(i) for i in [2,3,4,5,6,7,8,9])
{8, 2, 4, 5, 6}

1 にいるとき、次にいけるボタンは 8, 2, 4, 5, 6 だ。なお見ての通り順序は保持されない。 というのも、set は集合演算に特化されていて、要素の個数や順序といった概念を管理しないからだ。 ま、今回は探索順序はどうでもいいので、そんなことは気にしない。気にする必要があれば、結果に sorted を掛けるといいだろう。

使いやすいように関数を定義しておこう。

def candidate(i, rem):
    return rem - set(blocklist.get(i, {}).get(n) for n in rem)

こんな関数定義でもコード片をコピー&ペーストすれば問題なく認識してくれる。

定義を更新できたら動作を確認しよう。

>>> candidate(1, set([2,3,4,5,6,7,8,9]))
{8, 2, 4, 5, 6}
>>> candidate(1, set([2,3,4,6,7,8,9]))
{8, 9, 2, 4, 6}

問題なさそうだ。あとはひたすらリストアップをすればよいのだった。

def nextList(i, sel, rem):
    return sum(
        (nextList(s, sel + [s], rem - set([s])) for s in candidate(i, rem)),
        [sel] if 4 <= len(sel) else [])

Haskell 版と全く同じだ。 第一引数が「今選択しているボタン」、第二引数が「今まで選択してきたボタン」、第三引数が「未選択のボタン」である。 今回は既に 4 ボタン以上選択済みの場合も考慮に入れてある。 Python の 3 項演算子は順序が独特だが、後置 if だと思えばよい。

sum 関数は、Haskell でいうところの concat 相当として使っている。

>>> sum([[1,2],[3,4]], [])
[1, 2, 3, 4]

第二引数が「初期値」で、この部分に 4 ボタン以上選択済みだった場合の結果も入れ込んだ。 おかげで関数本体は 1 行だけである(横に長くなってしまったので折り返してはいるが)。

ところで Python の話をしながら突然 Haskell に戻るが、これを見せられれば当然、Haskell でも同等のことができることに気づく。

nextList :: Int -> [Int] -> [Int] -> [[Int]]
nextList n sel rem =
    foldr (++) (if 4 <= length sel then [sel] else [])
    [nextList s (sel ++ [s]) (rem \\ [s]) | s <- candidate n rem]

実は終了条件としていた nextList _ sel [] = [sel] も不要である。 なぜならその場合も foldr の初期値に結果が入り、内包表記が空になることで同等の処理が達成されるからである。

話が逸れた。Python に戻ろう。まず nextList 関数の動作確認。

>>> for p in nextList(6, [1,2,3,4,5,6], set([7,8,9])): print(p)
...
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 8]
[1, 2, 3, 4, 5, 6, 8, 9]
[1, 2, 3, 4, 5, 6, 8, 9, 7]
[1, 2, 3, 4, 5, 6, 8, 7]
[1, 2, 3, 4, 5, 6, 8, 7, 9]
[1, 2, 3, 4, 5, 6, 9]
[1, 2, 3, 4, 5, 6, 9, 8]
[1, 2, 3, 4, 5, 6, 9, 8, 7]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

順序はバラバラだが、結果セットはあっている。だめなパターン [...,7,9,8] および [...,9,7,8] もちゃんと取り除かれている。

では全力で数え上げよう。

def allList():
    return nextList(0, [], frozenset(range(1, 10)))

コピー&ペーストすればすぐに試せる。

>>> len(allList())
389112

やったね。

コード全体

完成したコード全体は下記の通り。

#!/usr/bin/python3
blocklist = {
    1: {2: 3, 4: 7, 5: 9},
    2: {5: 8},
    3: {2: 1, 5: 7, 6: 9},
    4: {5: 6},
    5: {},
    6: {5: 4},
    7: {4: 1, 5: 3, 8: 9},
    8: {5: 2},
    9: {5: 1, 6: 3, 8: 7},
}

def candidate(i, rem):
    return rem - set(blocklist.get(i, {}).get(n) for n in rem)

def nextList(i, sel, rem):
    return sum(
        (nextList(s, sel + [s], rem - set([s])) for s in candidate(i, rem)),
        [sel] if 4 <= len(sel) else [])

def allList():
    return nextList(0, [], frozenset(range(1, 10)))

print(len(allList()))

わずか 25 行。やるな、Python。

作った玩具で遊ぶ

さて、Haskell でやったのと同じように Python でも interactive shell で遊んでみることができる。 Haskell のようについ allList() を各場所に埋め込みたくなるが、 Python でそれをすると関数呼出し毎にリストの再構築を行うため、極めて効率が悪い。 従って、メモリは使用するにせよ、一回明示的に変数に代入すると良い。

>>> A = allList()

準備完了。最初の 10 件を表示。

>>> for p in A[:10]: print(p)
...
[1, 8, 3, 2]
[1, 8, 3, 2, 9]
[1, 8, 3, 2, 9, 4]
[1, 8, 3, 2, 9, 4, 5]
[1, 8, 3, 2, 9, 4, 5, 6]
[1, 8, 3, 2, 9, 4, 5, 6, 7]
[1, 8, 3, 2, 9, 4, 5, 7]
[1, 8, 3, 2, 9, 4, 5, 7, 6]
[1, 8, 3, 2, 9, 4, 7]
[1, 8, 3, 2, 9, 4, 7, 5]

順序がバラバラなのは、先に言及した通り、次へ遷移する要素を選択するために set を使っているためだ。

続いて、開始ボタン位置によるパターン数を数えてみよう。

>>> len(filter(lambda x: x[0] == 1, A))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: object of type 'filter' has no len()

...おっと、ジェネレータに len は適用できない。ジェネレータの個数を数えるには下記のようなイディオムがあるらしい。

>>> sum(1 for _ in A)
389112

なるほど。では改めて。

>>> sum(1 for x in A if x[0] == 1)
38042
>>> sum(1 for x in A if x[0] == 2)
43176
>>> sum(1 for x in A if x[0] == 3)
38042
>>> sum(1 for x in A if x[0] == 4)
43176
>>> sum(1 for x in A if x[0] == 5)
64240

当然 Haskell 版と同じ結果が得られる。

同じく終わりも調べよう。

>>> for p in ((x, sum(1 for l in A if l[-1] == x)) for x in range(1,10)):
...     print(p)
...
(1, 54374)
(2, 37144)
(3, 54374)
(4, 37144)
(5, 23040)
(6, 37144)
(7, 54374)
(8, 37144)
(9, 54374)

同様の結果が得られているようだ。

開始と終了で数えるのも同じようにできる。

>>> max((((x,y), sum(1 for l in A if l[0] == x and l[-1] == y))
... for x in range(1,10) for y in range(1,10) if x != y), key=lambda a: a[1])
((5, 1), 9620)

Haskell 版とは違い角のボタンが 9 ではなく 1 になっているが、いずれにせよパターン数は同じだ。

>>> min((((x,y), sum(1 for l in A if l[0] == x and l[-1] == y))
... for x in range(1,10) for y in range(1,10) if x != y), key=lambda a: a[1])
((1, 5), 2688)

こちらも同様。角から初めて中央で終わるのは 2688 パターンだ。

ボタン数でパターンを数える。

>>> for p in ((x, sum(1 for l in A if len(l) == x)) for x in range(4,10)):
...     print(p)
...
(4, 1624)
(5, 7152)
(6, 26016)
(7, 72912)
(8, 140704)
(9, 140704)

そして最後、乱択。

>>> from random import randint
>>> A[randint(0, len(A) - 1)]
[5, 9, 2, 3, 1, 8, 4, 6, 7]

もちろん実行ごとに違うリストが得られる。乱数生成は IO モナドに縛られない Python の方が手間が少ないのは違いない。

このブログ記事について

このページは、1024が2011年10月17日 22:00に書いたブログ記事です。

ひとつ前のブログ記事は「遅延評価とメモ化は別物(LINQ編)」です。

次のブログ記事は「C++ で Android の指リストパターンを数え上げる」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ