プログラミングの備忘録

プログラムをつくる過程を残すもの

pythonの備忘録 -itertools-

こんにちは。
今回は、itertoolsに頼らないようにするための記事です。


Project Eulerをやっていたときに、このような問題が登場しました。

projecteuler.net

この問題は、「0123456789」の辞書式順列の中で100万番目のものは何か、という問題です。
(以降、Project EulerのProblem 24の解法に一部触れるので、先に自分で解きたいという方はどうぞ。)


これを解くにあたり、自分は辞書式順列をつくってその100万番目の要素を取り出せば良いだろうと考えたのですが、その辞書式順列をつくるのに苦労し、結局モジュールの「itertools」を使うことにしました。

taq.hatenadiary.jp


個人的なこだわり(?)なのですが、できるだけ自分で書いたもの(中身が理解できたもの)を使ってコードを書くようにしているので、特に今回使ったpermutations()についてはどういう処理を行っているか見ることにしました。

ですが、理解できず。

docs.python.org


検索もかけていたのですが、そのときは「順列 python」などと調べていたので、全てitertoolsを使ったものでした。


しばらく経った今、他の言語ではどう書いているのだろうと思って「順列 プログラム」と調べてみると、自分が探していたものが見つかり、結果(全く同じものではありませんが)理解できたので記事にしています。

ついでに、他の問題で使ったことのある関数についても実装してみました。


目次


itertoolsとは

そもそもitertoolsとは何かというと、「iter」が(おそらく)「反復可能」という意味の「iterable」に由来することからもわかるように、何かしらfor文でループできるものをつくる関数がつまったものです。

pythonでモジュールを使うときはまずインストールする必要があるので、

pip install itertools

などを実行してインストールしておきます。
(1度やればOKです。)


例えば、「0, 1, 2」という数字の並べ方を全通り欲しいというときには、

import itertools

for i in permutations([0, 1, 2]):
    print(i)

と書くと、[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0] が出力されます。

順列を全て得られると同時に、(引数が辞書式順序であれば)その順番は辞書式になっています。


中身の理解

では、自分なりに中身を理解した上で書いたバージョンを載せておきます。

permutations()

重複無しの順列を出す関数です。

def perms(it):
    n = len(it)
    a = [i for i in it]
    
    if n <= 1:
        return [a]
    
    perm = []
    for i in range(n):
        a1 = [a[i]]
        a2 = a[:i] + a[i+1:]

        for j in perms(a2):
            perm.append(a1 + j)
    
    return perm


s = '012'
print(perms(s))


引数として反復可能なものitをとり、それを配列aに入れます。
aの1文字目a1 = [a[i]]とそれ以外a2 = a[:i] + a[i+1:]に分け、a2についてはpermutations()に入れることで再帰します。
順列ができたら1文字目a1と残りの部分を並び替えたものjを結合して、配列permに入れます。

'012'について実行すると、[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]と出力されました。


書くにあたっては、順列を列挙するプログラム - keroxpのScrapbox を参考にさせていただきました。


これをProject Euler -Problem 21~30- - プログラミングの備忘録での解法に適用してProject EulerのProblem 24を解いてみると、正しい答えが出力されました。

ただ、一度全ての順列を求めてから答えの計算を行うのでperms('0123456789')の配列には$10! = 3628800$個の要素があることになります。
必要なのは100万番目までなので、2/3くらい無駄です。


そこで、itertoolsのpermutations()のように、求めた順列を適宜取り出せるようにすれば無駄がなくなりそうです。

def perms(it):
    n = len(it)
    a = [i for i in it]
    
    if n <= 1:
        yield it
    
    for i in range(n):
        a1 = [a[i]]
        a2 = a[:i] + a[i+1:]

        for j in perms(a2):
            yield a1 + j


s = '0123'
for i in perms(s):
    print(i)


returnではそれ以下に処理が書いてあってもreturnした時点で関数の計算が終わってしまいます。
しかしyieldでは、それが呼び出されたときに関数の計算を一度止めて出力し、再びその続きから計算をすることができます。
(関数外でいうところの、無限ループ内でprint()を使って出力する感覚に近いと思います。)


yieldを使った場合は、

s = '0123'
for i in perms(s):
    print(i)

のようにfor文として使うことになります。

print(perms(s))としても<generator object perms at 0x00000221BEEE2890>などと返されるのみです。


combinations()

重複無しの組み合わせを出す関数です。

こちらは使ったことはありませんが、いずれ使うだろうと思ったので書いておきました。

def combs(it, r):
    n = len(it)
    a = [i for i in it]
    
    if n == 0 or r == 0 or n < r:
        #return []
        yield []
    elif n == 1 or n == r:
        #return a
        yield a
    else:
        #comb = []
        for i in range(1, 2**n):
            pre = []
            for j in range(len(bin(i))):
                if i>>j & 1:
                    pre.append(a[j])

            if len(pre) == r:
                #comb.append(pre)
                yield pre
    #return comb
    
    
s = 'abcd'
r = 2
for i in combs(s, r):
    print(i)      


AtCoder Beginner Contest 249 - プログラミングの備忘録の問題Cの部分でやった「bit全探索」を使って、「1」を選ぶ、「0」を選ばないに対応させて組み合わせpreをつくります。
そして、選ぶ数rと同じ個数だけ選ばれたものであればyieldします。


コメントアウトした部分を戻してyieldコメントアウトすれば、全組み合わせを配列combとして返すようにもできます。

組み合わせの順序は微妙に辞書式からずれていますが、sort()など使えば辞書式でも出力できると思います。


combinations_with_replacement()

重複ありの組み合わせを出す関数です。

これはProblem 49で使いました。

taq.hatenadiary.jp

def combsWithRep(it, r):
    n = len(it)
    a = [i for i in it]
    
    if n == 0 or r == 0:
        yield []
    elif n == 1:
        yield a
    else:
        for i in range(n):
            a1 = [a[i]]
            a2 = a[i:]

            for j in combsWithRep(a2, r-1):
                pre = a1 + j
                if len(pre) < r:
                    for k in range(r-len(pre)):
                        pre.append(a[n-1])
                yield pre


s = 'abc'
r = 2
for i in combsWithRep(s, r):
    print(i)       


形はperms()似ていますが、a2a1でとった文字以降のものだけを指定しています。
これにより同じ組み合わせが出ないようになっています。

また、できた組み合わせpreの長さがrに満たない場合があり、足りないものはitの最後の文字だとわかったので、とりあえずはpre.append(a[n-1])で足しています。


作成にあたっては重複組み合わせを列挙(C++)→追記にPythonコード - Qiitaを参考にさせていただきました。


これをProject Euler -Problem 41~50- - プログラミングの備忘録での解法に適用してProject EulerのProblem 49を解いてみると、正しい答えが出力されました。


まとめ

以上、モジュールitertoolsのpermuations()combinations()combinations_with_replacement()について自力でできるように関数をつくりました。