[解決!Python]順列や組み合わせを取り出したり、総数を計算したりするには解決!Python

mathモジュールのperm/comb関数、itertoolsモジュールのpermutations/combinations関数を使い、順列や組み合わせの総数や組を得られる。

» 2021年12月14日 05時00分 公開
[かわさきしんじDeep Insider編集部]

この記事は会員限定です。会員登録(無料)すると全てご覧いただけます。

「解決!Python」のインデックス

連載目次

import math
import itertools

# 順列の総数の計算と順列の取得
n = math.perm(4, 2)
print(n)  # 12

t = list(itertools.permutations(range(4), 2))
print(t)
# 出力結果:
#[(0, 1), (0, 2), (0, 3), (1, 0), (1, 2), (1, 3), (2, 0), (2, 1), (2, 3),
#(3, 0), (3, 1), (3, 2)]
print(len(t))  # 12

# 組み合わせの総数の計算と組み合わせの取得
n = math.comb(4, 2)
print(n)  # 6

t = list(itertools.combinations(range(4), 2))
print(t)  # [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
print(len(t))  # 6

# 順列の総数を計算する関数を定義
def perm(n, k):  # n×(n-1)×(n-2)×……×(n-k+2)×(n-k+1)を計算する方法
    if n < k:
        return 0

    result = 1
    for num in range(k):
        result *= (n - num)  # 5-0=5, 5-1=4, 5-2=3 (n = 5, k = 3)
    return result

def fact(n):  # math.factorial関数を使ってもよい
    result = 1
    for n in range(1, n+1):
        result *= n
    return result

def perm2(n, k):  # 組み合わせの総数= fact(n) // fact(n-k)の公式を使う方法
    if n < k:
        return 0

    return fact(n) // fact(n - k)

for n in range(4, 7):
    print(f'{n}P2: {math.perm(n, 2)}, {perm(n, 2)}, {perm2(n, 2)}')
    print(f'{n}P3: {math.perm(n, 3)}, {perm(n, 3)}, {perm2(n, 3)}')
# 出力結果
#4P2: 12, 12, 12
#4P3: 24, 24, 24
#5P2: 20, 20, 20
#5P3: 60, 60, 60
#6P2: 30, 30, 30
#6P3: 120, 120, 120

# 組み合わせの総数を計算する関数を定義
def comb(n, k):
    if n < k:
        return 0
    elif n == k or k == 0:
        return 1

    return perm(n, k) // fact(k)

for n in range(4, 7):
    print(f'{n}C2: {math.comb(n, 2)}, {comb(n, 2)}')
    print(f'{n}C3: {math.comb(n, 3)}, {comb(n, 3)}')
# 出力結果
#4C2: 6, 6
#4C3: 4, 4
#5C2: 10, 10
#5C3: 10, 10
#6C2: 15, 15
#6C3: 20, 20


順列の総数の計算と順列の取得

 順列とは「n個の要素からなる集合(n元集合)からk個の要素(元)を重複なし、並び順を考慮して取り出して並べたもの」と考えられる(並び順を考慮とは、以下の例の(0, 1)と(1, 0)は別の並び順と考えるという意味)。

 例えば、「0, 1, 2, 3」という4要素の集合から2個を重複なしで、並び順を考慮して取り出そうとすると「(0, 1), (0, 2), (0, 3), (1, 0), (1, 2), (1, 3), (2, 0), (2, 1), (2, 3), (3, 0), (3, 1), (3, 2)」という12個の順列があることが分かる。

 順列の総数はmathモジュールのperm関数を使うことで取得できる。以下は4要素の集合から2個の要素を取り出したときの順列の総数を求める例だ。なお、math.perm関数と後で紹介するmath.comb関数はPython 3.8で追加された(それよりも前のバージョンのPythonを使っているのであれば、独自に関数を定義するなどの方法がある。独自の関数の定義については本稿の後半を参照のこと)。

import math

n = math.perm(4, 2)
print(n)  # 12


 また、itertoolsモジュールのpermutations関数を使うと(実際にはpermutationsクラス)、順列を列挙するイテレーターとして利用できるオブジェクトを取得できる。以下は「0, 1, 2, 3」を要素とする集合から2個を重複なし、並び順を考慮して列挙するイテレーターを取得する例だ(list関数で順列の全要素をリストの要素としている)。

import itertools
t = list(itertools.permutations(range(4), 2))
print(t)
# 出力結果:
#[(0, 1), (0, 2), (0, 3), (1, 0), (1, 2), (1, 3), (2, 0), (2, 1), (2, 3),
#(3, 0), (3, 1), (3, 2)]
print(len(t))  # 12


 得られたリストの要素数を調べると、math.perm関数で取得した順列の総数と一致していることを確認してほしい。

組み合わせの総数の計算と組み合わせの取得

 組み合わせとは「n個の要素からなる集合からk個の要素(元)を重複なし、並び順を考慮しないで取り出して並べたもの」と考えられる。

 例えば、「0, 1, 2, 3」という4要素の集合から2個を重複なしで、並び順を考慮せずに取り出そうとすると「(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)」という6個の組み合わせがあることが分かる(順列とは異なり、(0, 1)と(1, 0)は同じものと考えるので、この組み合わせには「(1, 0)」が含まれていない)。

 組み合わせの総数はmathモジュールのcomb関数を使うことで取得できる。以下は4要素の集合から2個の要素を取り出したときの組み合わせの総数を求める例だ。

n = math.comb(4, 2)
print(n)  # 6


 順列と同様、itertoolsモジュールには組み合わせを列挙するイテレーターを取得するcombinations関数もある。使用例を以下に示す。

t = list(itertools.combinations(range(4), 2))
print(t)  # [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
print(len(t))  # 6


順列の総数を計算する関数を定義

 n個の要素からなる集合からk個の要素を取り出して得られる順列の総数をnPkとすると、これは次のような計算式で計算できる。

  • nPk=n×(n−1)×(n−2)×……×(n−k+1)

 4個の集合から2個の要素を取り出すのであれば、次のような計算になる。

  • 4×(4−2+1)=4×3=12

 最初に4つの中から1つを選び、次に残った3つの中から1つを選ぶので、その順列の総数(並べ方の種類)は4×3で得られるということだ。この考え方を関数にしたものを以下に示す。

def perm(n, k):  # n×(n-1)×(n-2)×……×(n-k+2)×(n-k+1)を計算する方法
    if n < k:
        return 0

    result = 1
    for num in range(k):
        result *= (n - num)  # 4-0=4, 4-1=3 (n = 4, k = 2)
    return result


 集合の数よりも取り出す数が大きいときには取り出しようがないので0を返しているが、その後は上で述べた通りのやり方で計算している。

 一方、階乗(1からnまでの整数を掛け合わせた値。nの階乗=1×2×……×nを「n!」と表現する)を使うと、順列の総数nPkは以下の計算式で得られることも知られている。

  • nPk=n!/(n−k)!

 これを使っても順列の総数は計算できる。以下にこの方法で計算する関数のコードを示す。

def fact(n):  # math.factorial関数を使ってもよい
    result = 1
    for n in range(1, n+1):
        result *= n
    return result

def perm2(n, k):  # 組み合わせの総数= fact(n) // fact(n-k)の公式を使う方法
    if n < k:
        return 0

    return fact(n) // fact(n - k)


 math.perm関数を含む3つの関数を使って順列の総数を計算する例を以下に示す。

for n in range(4, 7):
    print(f'{n}P2: {math.perm(n, 2)}, {perm(n, 2)}, {perm2(n, 2)}')
    print(f'{n}P3: {math.perm(n, 3)}, {perm(n, 3)}, {perm2(n, 3)}')
# 出力結果
#4P2: 12, 12, 12
#4P3: 24, 24, 24
#5P2: 20, 20, 20
#5P3: 60, 60, 60
#6P2: 30, 30, 30
#6P3: 120, 120, 120


組み合わせの総数を計算する関数を定義

 n個の要素からなる集合からk個の要素を重複なし、並び順を考慮せずに取り出して得られる組み合わせの総数をnCkとすると、これは次のような計算式で計算できる。

  • nCknPk/k!

def comb(n, k):
    if n < k:
        return 0
    elif n == k or k == 0:
        return 1

    return perm(n, k) // fact(k)


 順列の総数の計算と同様、集合の数よりも取り出す数が大きいときには取り出しようがないので0を返し、nとkが等しい(集合から全ての要素を取り出す)ときと、kが0である(集合から1つも要素を取り出さない)ときには1を返しているが、その後は上で述べた通りのやり方で計算している。

 math.comb関数と独自に定義したcomb関数を使って組み合わせの総数を計算する例を以下に示す。

for n in range(4, 7):
    print(f'{n}C2: {math.comb(n, 2)}, {comb(n, 2)}')
    print(f'{n}C3: {math.comb(n, 3)}, {comb(n, 3)}')
# 出力結果
#4C2: 6, 6
#4C3: 4, 4
#5C2: 10, 10
#5C3: 10, 10
#6C2: 15, 15
#6C3: 20, 20


「解決!Python」のインデックス

解決!Python

Copyright© Digital Advantage Corp. All Rights Reserved.

スポンサーからのお知らせPR

注目のテーマ

Microsoft & Windows最前線2025
AI for エンジニアリング
ローコード/ノーコード セントラル by @IT - ITエンジニアがビジネスの中心で活躍する組織へ
Cloud Native Central by @IT - スケーラブルな能力を組織に
システム開発ノウハウ 【発注ナビ】PR
あなたにおすすめの記事PR

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。