重複順列問題を解く

高校数学復習の機会

子供に復習させるとかではなく、自分の話。実際の話、中学受験は難しいと言われるけど、実際に自分で問題を見てみるまではわからなかったんですね。特に「算数」なんかは甘く見ていたのですが、意外と難しい。中学・高校レベルの数学で出てくるような問題もあるし、おまけに、自分が色々と忘れていたり(理解が適当だった証拠で)して、参考書を見直したりして、どっちが勉強しているんだかわからなかったりします。
でも、こういう機会を得たのもありがたい事だと思って取り組んでみると、結構おもしろいんですよね。あまり真面目な学生ではなかった過去の自分に、もったいないよ、と言ってやりたい。

場合の数が出てこない

中学受験では場合の数の問題は普通に出てきますが、確率とかも学生時代に適当にやったものの一つでしたから、解き方がわかっても用語とかが曖昧だったりして先日もあわてて参考書を見直しました。

家族5人で食事に行きました。そのレストランにはメニューが4種類あります。1人が注文するのはメニューの中から1種類だけです。
家族全体の注文の仕方は全部で何種類あるでしょうか？

こういう問題の答えが「4の5乗」であることはすぐわかるのですが、こういう場合の数を何と言ったけ？というのが出てこない。調べてやっと「重複順列」だと思い出す始末で、何というかダメダメです。

順列をつくるとき、いくつかの要素を落として使わないこと（omission; 省略）やいくつかの要素を何度も使うこと（duplication, repetition; 重複）ができるが、取り出す要素に重複を許す順列を重複順列（ちょうふくじゅんれつ、repeated permutation）と呼んで特に区別する場合がある。

順列 - Wikipedia

調べたものは解いておく

調べたうえで気分がのればコードも書くと忘れないですね。以前も書きましたけど、総当たり的な処理はコンピュータの得意技ですよね。

# coding: utf-8
"""
重複順列 - repeated permutation
指定されたパラメータで重複順列を作成し、その結果を返す。
"""

def repeat_perm(items, nrept):
    """
    重複順列ジェネレータ版.
    最後まで行ったところで空リストを返し、戻る際に順番に追加していく。
      $param items 選択可能な要素リスト
      $param nrept 選択する数
      $return 重複順列を１つずつ返す。
    """
    if (not items) or (nrept < 0):
        raise ValueError('Invalid arguments %s * %d' % (items, nrept))

    if nrept == 0:
        yield []
    else:
        # 全ての選択可能な要素について処理する
        for i in items:
            # repeat_perm()自身がジェネレータなので、再帰的に
            # 終端から戻ってくる値をさらに呼び出し元に戻す。
            for gen in repeat_perm(items, (nrept - 1)):
                yield [i] + gen

def repeat_perm2(items, nrept, res=[]):
    """
    重複順列ジェネレータ版.
    省略可能引数に結果を積み上げていくやりかた。(わかりにくいかな)
      $param items 選択可能な要素リスト
      $param nrept 選択する数
      $param res   生成中の順列を保持するためのリスト
      $return 重複順列を１つずつ返す。
    """
    if (not items) or (nrept < 0):
        raise ValueError('Invalid arguments %s * %d' % (items, nrept))

    if nrept == 0:
        yield tuple(res)
    else:
        # 全ての選択可能な要素について処理する
        for i in items:
            # repeat_perm()自身がジェネレータなので、再帰的に
            # 終端から戻ってくる値をさらに呼び出し元に戻す。
            for gen in repeat_perm2(items, (nrept - 1), (res + [i])):
                yield gen

##############################################################

if __name__ == "__main__":
    #PTRN = range(2)
    PTRN = ('apple', 'orange')
    SLCT = 3
    # print tuple(repeat_perm2(PTRN, SLCT))
    for x in repeat_perm(PTRN, SLCT):
        print x

実行した結果は以下のとおり。

bash-3.2$ python ./rperm.py 
['apple', 'apple', 'apple']
['apple', 'apple', 'orange']
['apple', 'orange', 'apple']
['apple', 'orange', 'orange']
['orange', 'apple', 'apple']
['orange', 'apple', 'orange']
['orange', 'orange', 'apple']
['orange', 'orange', 'orange']

ちゃんと動いているようです。こういう、ちょっとした気晴らしプログラミングは良いですね。