Python3のForループ（２）順列・組合せと組み合わせて内部条件チェックをはぶく応用技

目次

Forループと順列・組合せ

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で解くことを考えます。

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

順列を使うと嬉しいケース ：使わない場合のForループ 

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

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 itertools as it
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)
print(len(lst)) 

同じ人を重複させないために、上位のループで対象になった人を省いて、下のループを回してます。

ごちゃごちゃしてますし、あまりスマートとはいえません。 

順列を使うと嬉しいケース ：使った場合のForループ 

でも、これを「順列」を使って書き直すと、以下のようにスマートにできます。

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))

いい感じです。 

組合せを使うと嬉しいケース 

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

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

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

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

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

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

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

上記は

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

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

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

さて。

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

組合せを使うと嬉しいケース：使わない場合 のForループ

基本は上の順列と同じですが、同じ組み合わせのものがすでにあれば処理しないというチェックが追加で必要になります。

import itertools as it
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(isMatch(t)):
                    lst.append(t)

print(len(lst))

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

組合せを使うと嬉しいケース：使う場合のForループ 

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

seedの5人の中から、3人を選ぶ組合せなので「combinations(seed2,3)」ということになります。

import itertools as it
seed2 = ['a','b','c','d','e']
lst2 = []
for x1,x2,x3 in list(it.combinations(seed2,3)):
     t = (x1,x2,x3)
     if(isMatch(t)):
         lst2.append(t)

print(len(lst2)) 

スマートですねえ。

実際、ループを回して、内部で条件チェックをして処理対象外をはぶくみたいな処理が、この順列・組合せを使ったループに変更するだけで劇的にスッキリかけてしまうということは結構あるので、引き出しのひとつとしては有効です。 

ではでは。