PythonのForループのスマートな書き方まとめ（２）順列・組合せを使う

Pythonのforループで順列・組合せの考え方を導入すると、すっきりスマートにかけるようになるケースがあるので、まとめておきます。

f:id:arakan_no_boku:20181124131221j:plain

順列・組合せの復習から。

備忘をかねて復習から。

順列とは。

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）

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

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

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

順列を使った場合

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

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

さて。

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

組合せを使わない例

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

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

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

組合せを使う例

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

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

スマートですねえ。

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