TIM Labs

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

| コメント(0) | トラックバック(0)

えっ。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 の方が手間が少ないのは違いない。

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/268

コメントする

このブログ記事について

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

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

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

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