Pythonで階乗・順列・組み合わせを完全マスター【計算・生成完全ガイド】
Pythonを使えば、階乗、順列、組み合わせの計算と生成を簡単に行うことができます。この記事では、mathモジュールとitertoolsモジュールを活用した効率的な計算方法から実践的な応用まで詳しく解説します。
階乗（Factorial）の計算
math.factorial()の使用
import math
# 基本的な階乗計算
numbers = [0, 1, 5, 10, 15]
print("n | n!")
print("-" * 15)
for n in numbers:
factorial_result = math.factorial(n)
print(f"{n:2} | {factorial_result}")
# 大きな数の階乗
print(f"\n20! = {math.factorial(20):,}")
print(f"50! = {math.factorial(50):,}")
再帰的な階乗実装
def factorial_recursive(n):
"""再帰による階乗計算"""
if n < 0:
raise ValueError("階乗は非負整数で定義されます")
if n <= 1:
return 1
return n * factorial_recursive(n - 1)
def factorial_iterative(n):
"""反復による階乗計算"""
if n < 0:
raise ValueError("階乗は非負整数で定義されます")
result = 1
for i in range(2, n + 1):
result *= i
return result
# 性能比較
import time
n = 1000
start = time.time()
result1 = math.factorial(n)
time1 = time.time() - start
start = time.time()
result2 = factorial_iterative(n)
time2 = time.time() - start
print(f"math.factorial({n}): {time1:.6f}秒")
print(f"自作関数({n}): {time2:.6f}秒")
順列（Permutation）の計算
math.perm()による計算（Python 3.8+）
import math
# nPr = n! / (n-r)!
def manual_permutation(n, r):
"""手動での順列計算"""
if r > n or r < 0:
return 0
return math.factorial(n) // math.factorial(n - r)
# Python 3.8以降のmath.perm()を使用
if hasattr(math, 'perm'):
test_cases = [(5, 2), (10, 3), (7, 7), (5, 0)]
print("n | r | nPr (math.perm) | nPr (手動)")
print("-" * 40)
for n, r in test_cases:
perm1 = math.perm(n, r)
perm2 = manual_permutation(n, r)
print(f"{n:2} | {r:2} | {perm1:14} | {perm2:8}")
else:
print("math.perm()は利用できません（Python 3.8未満）")
順列の生成（itertools.permutations）
import itertools
def generate_permutations(items, r=None):
"""
アイテムの順列を生成
r: 選択する要素数（デフォルトは全要素）
"""
if r is None:
r = len(items)
return list(itertools.permutations(items, r))
# 文字の順列
letters = ['A', 'B', 'C']
perms = generate_permutations(letters, 2)
print(f"文字 {letters} の2つ選ぶ順列:")
for i, perm in enumerate(perms, 1):
print(f"{i:2}: {''.join(perm)}")
# 数字の順列
numbers = [1, 2, 3, 4]
all_perms = generate_permutations(numbers, 3)
print(f"\n数字 {numbers} の3つ選ぶ順列の総数: {len(all_perms)}")
組み合わせ（Combination）の計算
math.comb()による計算（Python 3.8+）
import math
def manual_combination(n, r):
"""手動での組み合わせ計算: nCr = n! / (r! * (n-r)!)"""
if r > n or r < 0:
return 0
if r == 0 or r == n:
return 1
# 計算を効率化：r > n-r の場合、r = n-r に変更
r = min(r, n - r)
result = 1
for i in range(r):
result = result * (n - i) // (i + 1)
return result
# Python 3.8以降のmath.comb()を使用
if hasattr(math, 'comb'):
test_cases = [(5, 2), (10, 3), (52, 5), (100, 2)]
print("n | r | nCr (math.comb) | nCr (手動)")
print("-" * 42)
for n, r in test_cases:
comb1 = math.comb(n, r)
comb2 = manual_combination(n, r)
print(f"{n:3} | {r:2} | {comb1:14,} | {comb2:14,}")
else:
print("math.comb()は利用できません（Python 3.8未満）")
組み合わせの生成（itertools.combinations）
import itertools
def generate_combinations(items, r):
"""アイテムの組み合わせを生成"""
return list(itertools.combinations(items, r))
# 文字の組み合わせ
letters = ['A', 'B', 'C', 'D']
combs = generate_combinations(letters, 2)
print(f"文字 {letters} の2つ選ぶ組み合わせ:")
for i, comb in enumerate(combs, 1):
print(f"{i:2}: {''.join(comb)}")
# 数字の組み合わせ
numbers = [1, 2, 3, 4, 5]
three_combs = generate_combinations(numbers, 3)
print(f"\n数字 {numbers} の3つ選ぶ組み合わせ:")
for comb in three_combs[:5]: # 最初の5つのみ表示
print(comb)
print(f"... 総数: {len(three_combs)}")
重複順列と重複組み合わせ
重複順列（Permutation with Repetition）
import itertools
def permutations_with_repetition(items, r):
"""重複を許す順列"""
return list(itertools.product(items, repeat=r))
# 重複順列の例
digits = [1, 2, 3]
dup_perms = permutations_with_repetition(digits, 2)
print("重複を許す順列 (1,2,3から2つ選択):")
for perm in dup_perms:
print(perm)
print(f"総数: {len(dup_perms)} = {len(digits)}^{2}")
重複組み合わせ（Combination with Repetition）
import itertools
def combinations_with_repetition(items, r):
"""重複を許す組み合わせ"""
return list(itertools.combinations_with_replacement(items, r))
# 重複組み合わせの例
colors = ['赤', '青', '緑']
dup_combs = combinations_with_repetition(colors, 2)
print("重複を許す組み合わせ (色から2つ選択):")
for comb in dup_combs:
print(comb)
# 重複組み合わせの総数公式: C(n+r-1, r)
n, r = len(colors), 2
expected = math.comb(n + r - 1, r)
print(f"総数: {len(dup_combs)} (期待値: {expected})")
実践的な応用例
パスワード生成の組み合わせ計算
import math
import string
def password_combinations():
"""パスワードの可能な組み合わせ数を計算"""
# 文字セットの定義
lowercase = string.ascii_lowercase # 26文字
uppercase = string.ascii_uppercase # 26文字
digits = string.digits # 10文字
symbols = "!@#$%^&*" # 8文字
charset_sizes = {
'小文字のみ': len(lowercase),
'小文字+大文字': len(lowercase) + len(uppercase),
'英数字': len(lowercase) + len(uppercase) + len(digits),
'英数字+記号': len(lowercase) + len(uppercase) + len(digits) + len(symbols)
}
password_lengths = [6, 8, 10, 12]
print("パスワードの組み合わせ数:")
print("文字セット".ljust(15), end="")
for length in password_lengths:
print(f"{length}桁".rjust(12), end="")
print()
print("-" * 65)
for charset_name, charset_size in charset_sizes.items():
print(charset_name.ljust(15), end="")
for length in password_lengths:
combinations = charset_size ** length
if combinations < 1e9:
print(f"{combinations:11,}".rjust(12), end="")
else:
print(f"{combinations:.2e}".rjust(12), end="")
print()
password_combinations()
宝くじの当選確率計算
import math
def lottery_probability():
"""宝くじの当選確率を計算"""
lotteries = [
("ロト6", 43, 6), # 43個から6個選択
("ロト7", 37, 7), # 37個から7個選択
("ミニロト", 31, 5), # 31個から5個選択
("ナンバーズ4", 10, 4, "重複順列") # 0-9から4桁
]
print("宝くじの当選確率:")
print("-" * 40)
for lottery in lotteries:
name = lottery[0]
if len(lottery) == 4 and lottery[3] == "重複順列":
# 重複順列の場合
combinations = lottery[1] ** lottery[2]
else:
# 通常の組み合わせ
n, r = lottery[1], lottery[2]
combinations = math.comb(n, r)
probability = 1 / combinations
print(f"{name}:")
print(f" 組み合わせ数: {combinations:,}")
print(f" 当選確率: 1/{combinations:,} = {probability:.2e}")
print(f" パーセント: {probability * 100:.8f}%")
print()
lottery_probability()
カードゲームの確率計算
import math
def poker_hand_probabilities():
"""ポーカーの役の確率を計算"""
total_hands = math.comb(52, 5) # 52枚から5枚選ぶ組み合わせ
# 各役の組み合わせ数（簡略化）
hands = {
'ロイヤルストレートフラッシュ': 4,
'ストレートフラッシュ': 36,
'フォーカード': 624,
'フルハウス': 3744,
'フラッシュ': 5108,
'ストレート': 10200,
'スリーカード': 54912,
'ツーペア': 123552,
'ワンペア': 1098240,
'ハイカード': 1302540
}
print("ポーカーの役の確率:")
print("-" * 50)
print(f"全組み合わせ数: {total_hands:,}")
print()
total_check = 0
for hand_name, count in hands.items():
probability = count / total_hands
total_check += count
print(f"{hand_name}:")
print(f" 組み合わせ数: {count:,}")
print(f" 確率: {probability:.6f} ({probability * 100:.4f}%)")
print()
print(f"合計確認: {total_check:,} (期待値: {total_hands:,})")
poker_hand_probabilities()
試験問題の組み合わせ
import itertools
import math
def exam_question_combinations():
"""試験問題の出題パターンを計算"""
# 問題カテゴリと問題数
categories = {
'数学': 20,
'物理': 15,
'化学': 12,
'英語': 18
}
# 各カテゴリから出題する問題数
questions_per_category = {
'数学': 5,
'物理': 3,
'化学': 2,
'英語': 4
}
print("試験問題の出題パターン:")
print("-" * 40)
total_combinations = 1
for category, total_questions in categories.items():
select_questions = questions_per_category[category]
combinations = math.comb(total_questions, select_questions)
total_combinations *= combinations
print(f"{category}:")
print(f" 問題数: {total_questions}問から{select_questions}問選択")
print(f" 組み合わせ: {combinations:,}通り")
print()
print(f"全体の組み合わせ数: {total_combinations:,}通り")
exam_question_combinations()
大きな数での効率的な計算
スターリングの公式による近似
import math
def stirling_approximation(n):
"""スターリングの公式による階乗の近似: n! ≈ √(2πn) * (n/e)^n"""
if n == 0:
return 1
return math.sqrt(2 * math.pi * n) * (n / math.e) ** n
def compare_factorial_methods(n):
"""階乗計算の精度と速度を比較"""
# 正確な値
exact = math.factorial(n)
# スターリングの近似
approx = stirling_approximation(n)
# 相対誤差
relative_error = abs(exact - approx) / exact * 100
print(f"n = {n}")
print(f"正確な値: {exact:,.0f}")
print(f"スターリング近似: {approx:,.0f}")
print(f"相対誤差: {relative_error:.4f}%")
print()
# 複数の値で比較
for n in [5, 10, 20, 50]:
compare_factorial_methods(n)
大きな組み合わせの効率的計算
import math
def efficient_combination(n, r):
"""大きな組み合わせを効率的に計算"""
if r > n - r:
r = n - r # より小さいrを使用
if r == 0:
return 1
result = 1
for i in range(r):
result = result * (n - i) // (i + 1)
return result
def log_combination(n, r):
"""対数を使った組み合わせ計算（オーバーフロー防止）"""
if r > n - r:
r = n - r
if r == 0:
return 0 # log(1) = 0
log_result = 0
for i in range(r):
log_result += math.log(n - i) - math.log(i + 1)
return log_result
# 大きな組み合わせの計算
n, r = 1000, 50
try:
# 通常の計算
result1 = efficient_combination(n, r)
print(f"C({n}, {r}) = {result1:,}")
# 対数計算
log_result = log_combination(n, r)
result2 = math.exp(log_result)
print(f"対数計算結果: {result2:,.0f}")
# math.comb()との比較（Python 3.8+）
if hasattr(math, 'comb'):
result3 = math.comb(n, r)
print(f"math.comb(): {result3:,}")
except OverflowError:
print("数値が大きすぎてオーバーフローしました")
パフォーマンス最適化
メモ化による高速化
from functools import lru_cache
@lru_cache(maxsize=None)
def memoized_factorial(n):
"""メモ化された階乗関数"""
if n <= 1:
return 1
return n * memoized_factorial(n - 1)
@lru_cache(maxsize=None)
def memoized_combination(n, r):
"""メモ化された組み合わせ関数"""
if r > n - r:
r = n - r
if r == 0:
return 1
return memoized_factorial(n) // (memoized_factorial(r) * memoized_factorial(n - r))
# パフォーマンステスト
import time
def performance_test():
numbers = [(100, 50), (200, 100), (300, 150)]
print("組み合わせ計算のパフォーマンス比較:")
print("-" * 50)
for n, r in numbers:
# 通常の計算
start = time.time()
result1 = efficient_combination(n, r)
time1 = time.time() - start
# メモ化された計算
start = time.time()
result2 = memoized_combination(n, r)
time2 = time.time() - start
print(f"C({n}, {r}):")
print(f" 通常の計算: {time1:.6f}秒")
print(f" メモ化計算: {time2:.6f}秒")
print(f" 結果の一致: {result1 == result2}")
print()
performance_test()
エラーハンドリングと検証
入力値の検証
def safe_factorial(n):
"""安全な階乗計算"""
if not isinstance(n, int):
raise TypeError("階乗の引数は整数である必要があります")
if n < 0:
raise ValueError("階乗は非負整数で定義されます")
if n > 1000: # 実用的な上限
raise ValueError("計算可能な範囲を超えています")
return math.factorial(n)
def safe_combination(n, r):
"""安全な組み合わせ計算"""
if not isinstance(n, int) or not isinstance(r, int):
raise TypeError("引数は整数である必要があります")
if n < 0 or r < 0:
raise ValueError("引数は非負整数である必要があります")
if r > n:
raise ValueError("rはn以下である必要があります")
return efficient_combination(n, r)
# テスト
test_cases = [
(5, safe_factorial),
(-1, safe_factorial),
(5.5, safe_factorial),
((10, 3), lambda x: safe_combination(*x)),
((3, 5), lambda x: safe_combination(*x))
]
for case, func in test_cases:
try:
if isinstance(case, tuple):
result = func(case)
print(f"safe_combination{case} = {result}")
else:
result = func(case)
print(f"safe_factorial({case}) = {result}")
except (TypeError, ValueError) as e:
print(f"エラー: {e}")
計算結果の検証
def verify_combination_identity(n, r):
"""組み合わせの恒等式を検証: C(n,r) = C(n,n-r)"""
comb1 = math.comb(n, r) if hasattr(math, 'comb') else efficient_combination(n, r)
comb2 = math.comb(n, n-r) if hasattr(math, 'comb') else efficient_combination(n, n-r)
print(f"C({n},{r}) = {comb1:,}")
print(f"C({n},{n-r}) = {comb2:,}")
print(f"恒等式成立: {comb1 == comb2}")
return comb1 == comb2
def verify_pascal_triangle(n):
"""パスカルの三角形の性質を検証: C(n,r) + C(n,r+1) = C(n+1,r+1)"""
print(f"パスカルの三角形の性質検証 (n={n}):")
for r in range(n):
left = math.comb(n, r) if hasattr(math, 'comb') else efficient_combination(n, r)
right = math.comb(n, r+1) if hasattr(math, 'comb') else efficient_combination(n, r+1)
sum_val = left + right
expected = math.comb(n+1, r+1) if hasattr(math, 'comb') else efficient_combination(n+1, r+1)
print(f" C({n},{r}) + C({n},{r+1}) = {left} + {right} = {sum_val}")
print(f" C({n+1},{r+1}) = {expected}")
print(f" 一致: {sum_val == expected}")
print()
# 恒等式の検証
verify_combination_identity(10, 3)
print()
# パスカルの三角形の検証
verify_pascal_triangle(5)
まとめ
Pythonの階乗・順列・組み合わせ機能は以下の特徴を持ちます：
math.factorial(),math.perm(),math.comb()による高速計算itertoolsモジュールによる実際の組み合わせ生成- 重複を許す場合の計算も完全サポート
- 大きな数値での効率的な計算手法
これらの組み合わせ論的関数は、確率計算、統計分析、暗号理論、ゲーム理論など、様々な分野で基礎となる重要な数学ツールです。適切なエラーハンドリングと効率的な実装を組み合わせて、実用的な問題解決に活用しましょう。
■プロンプトだけでオリジナルアプリを開発・公開してみた！！
■AI時代の第一歩！「AI駆動開発コース」はじめました！
テックジム東京本校で先行開始。
■テックジム東京本校
「武田塾」のプログラミング版といえば「テックジム」。
講義動画なし、教科書なし。「進捗管理とコーチング」で効率学習。
より早く、より安く、しかも対面型のプログラミングスクールです。
＜短期講習＞5日で5万円の「Pythonミニキャンプ」開催中。
＜月1開催＞放送作家による映像ディレクター養成講座
＜オンライン無料＞ゼロから始めるPython爆速講座
