順列・組合せでネストするループをすっきり書く／Python文法

目次

順列・組合せでネストするループをすっきり書く

Pythonのforループの中で順列・組合せを使います。

概要

縦列・組み合わせ

順列とは、A,B,C　の３つの文字から２つを取り出す時。以下のように、（A,B）と（B,A)を別のものとして数えるやり方です。

（A,B）（A,C）（B,A）（B,C）（C,A）（C,B）

組合せは 、以下のように（A,B）（B,A)は同じものとみなすやり方のことです。

（A,B）（A,C）（B,C）

順列・組合せの処理を通すと、ルールにそったペアのみを受け取ることができます。

つまり、Forループ内でルールにそっているかをチェックする必要がなくなります。

pythonにおける順列・組合せ 

順列と組合せは、Pythonだと、itertoolsというライブラリで提供されてます。

permutations（順列）と、combinations（組合せ）です。

上に書いた例をPythonで書くとこんな感じです。

import itertools as it

seed = ('a','b','c')

pmt = list(it.permutations(seed,2))
print(pmt)

cmt = list(it.combinations(seed,2))
print(cmt)

結果はこんな感じ。

順列

[('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]

組合せ

[('a', 'b'), ('a', 'c'), ('b', 'c')] 

これを使っていきます。 

順列を使うケーズ  

解決する問題

例えば、こんな問題です。

３つの一列に並んだ椅子があります。

一番前を（１）、真ん中を（２）、最後尾を（３）とします。

この椅子に、Ａさん、Ｂさん、Ｃさん、Ｄさん、Ｅさんの5人から3人がランダムに選ばれて座ります。

Ｃさん、Ｄさん、Ｅさんは、前後しても構いません。

でも、Aさんが座る時は必ず先頭でないとダメです。

Bさんは、Aさんがいる時だけ2番目で、Aさんがいないと必ず先頭です。

この序列を逆転して座らせることはできません。

この序列を満たす座り方は何通りありますか？

これをPythonで解くことを考えます。

すべての場合をつくして、序列条件に適合する並びだけをカウントする・・みたいなプログラムを解くことになります。

ネストしたループの実装例

まず、「序列条件に適合する」は、こんな関数で判断することにします。

def isMatch(t):
    if('a' not in t and 'b' not in t ):
        return 1
    else:
        if(t[0] == 'a' and (t[1] == 'b' or 'b' not in t)):
            return 1
        else:
            if(t[0] == 'b' and 'a' not in t):
                return 1
            else:
                return 0 

 引数の「t」は('a','b','c')みたいに３人の並びを示すtuppleです。

単純に以下の条件としてます。

• 'a','b'が両方いない時は序列順を気にしなくていいので常にOK
• 'a'が先頭の時は、'b'が2番目もしくは'b'がいなければOK
• 'b'が先頭の時は'a'がいなければOK
• 上記３つのパターン以外はNG

あとは、「すべての場合をつくして」の部分ですが、これを普通に書くと、こんな感じのループになります。

import copy

seed = ["a", "b", "c", "d", "e"]
lst = []
for x1 in seed:
    s1 = copy.copy(seed)
    s1.remove(x1)
    for x2 in s1:
        s2 = copy.copy(s1)
        s2.remove(x2)
        for x3 in s2:
            t = (x1, x2, x3)
            if isMatch(t):
                lst.append(t)
for t in lst:
    print(t)

同じ人を重複させないために、上位のループで対象になった人を省いて、下のループを回したり、ごちゃごちゃしていますが、結果はこうなりました。

('a', 'b', 'c')
('a', 'b', 'd')
('a', 'b', 'e')
('a', 'c', 'd')
('a', 'c', 'e')
('a', 'd', 'c')
('a', 'd', 'e')
('a', 'e', 'c')
('a', 'e', 'd')
('b', 'c', 'd')
('b', 'c', 'e')
('b', 'd', 'c')
('b', 'd', 'e')
('b', 'e', 'c')
('b', 'e', 'd')
('c', 'd', 'e')
('c', 'e', 'd')
('d', 'c', 'e')
('d', 'e', 'c')
('e', 'c', 'd')
('e', 'd', 'c')

一応、答えとしてはあっているように見えます。

順列を使ってスッキリと書く

上記を「順列」を使って書き直すと、こんな感じにすっきりします。

import itertools as it

seed = ['a','b','c','d','e']
lst2 = []
for x1,x2,x3 in list(it.permutations(seed,3)):
     t = (x1,x2,x3)
     if(isMatch(t)):
         lst2.append(t)

print(len(lst2))

isMatch()でチェックしているところは同じです。

答えも全く同じですが、試すべき組み合わせの生成部分が劇的にすっきりしました。

('a', 'b', 'c')
('a', 'b', 'd')
('a', 'b', 'e')
('a', 'c', 'd')
('a', 'c', 'e')
('a', 'd', 'c')
('a', 'd', 'e')
('a', 'e', 'c')
('a', 'e', 'd')
('b', 'c', 'd')
('b', 'c', 'e')
('b', 'd', 'c')
('b', 'd', 'e')
('b', 'e', 'c')
('b', 'e', 'd')
('c', 'd', 'e')
('c', 'e', 'd')
('d', 'c', 'e')
('d', 'e', 'c')
('e', 'c', 'd')
('e', 'd', 'c')

組み合わせを使うケーズ

解決すべき問題

組合せの場合は、並び順が違っても同一とみなします。

これが必要になるような問題はこんな感じ。

ある部門に5人の社員がいて、シフト勤務で業務をまわしています。

シフトは必ず3人で入る決まりです。

でも、以下の組み合わせは避けたいと思ってます。

• aさんとcさんは仲が悪いから、同じシフトを避けたい。
• bさんとdさんは夫婦なので同じシフトを避けたい

可能な組み合わせは何通りできるか？

上記は

• aさんcさんが一緒だとNG
• bさん dさんが一緒だとNG
• 上記以外はOK

ということなので、以下のように判定することにします。

def isMatch2(t):
    if(('a' in t) and ('c' in t)):
        return 0
    if(('b' in t) and ('d' in t)):
        return 0
    return 1    

さて。

これを使って 、こちらも普通にｆｏｒループを使って書いてみます。 

ネストしたループの実装例

基本は上の順列と同じです。

しかし、同じ組み合わせのものがすでにあれば処理しないチェックが必要です。

なので、生成したリストに同じ組み合わせがないかチェックする「isFirstCase()」なる関数を追加しています。

import copy

def isFirstCase(lst,tpl):
    for x in lst:
        if(set(x) == set(tpl)):
            return False
    return True    

seed = ["a", "b", "c", "d", "e"]
lst = []
for x1 in seed:
    s1 = copy.copy(seed)
    s1.remove(x1)
    for x2 in s1:
        s2 = copy.copy(s1)
        s2.remove(x2)
        for x3 in s2:
            t = (x1, x2, x3)
            if isFirstCase(lst, t):
                if isMatch2(t):
                    lst.append(t)
for t in lst:
    print(t)

順列よりもさらにややこしくて、スマートとは言えません。 

結果はこう出力されます。

('a', 'b', 'e')
('a', 'd', 'e')
('b', 'c', 'e')
('c', 'd', 'e')

組合せを使ってスマートに書く

これも組み合わせを使うと、スマートに書けます。

seedの5人の中から、3人を選ぶ組合せなので「combinations(seed2,3)」です。

import itertools as it
seed = ["a", "b", "c", "d", "e"]
lst2 = []
for x1, x2, x3 in list(it.permutations(seed, 3)):
    t = (x1, x2, x3)
    if isMatch2(t):
        lst2.append(t)

for t in lst2:
    print(t)

スマートです。

結果も同じ。

('a', 'b', 'e')
('a', 'd', 'e')
('b', 'c', 'e')
('c', 'd', 'e')

以上です。

こんな感じで、内部で条件チェックをして処理対象外をはぶくような処理が、順列・組合せを使うと劇的にスッキリかけることは意外にあります。

引き出しのひとつとしては有効かと思います。