Pythonで順列と組み合わせの勉強

AtCoder ABC183 Cに取り組みましたが、
残念ながら解くことができませんでした。

今回は公式解説に出ていた順列（と組み合わせ）について勉強したいと思います。

順列とは

はじめに順列について確認します。
順列とは「n個のなかからr個を順番に選ぶ」場合の数です。
例えば(1,2,3,4)の全4個のなかから3個を選ぶ順列は4P3のように表記し、その値は4×3×2 = 24通りとなります。
(1,2,3,4)のなかからひとつ目の数字の選び方は4通り、次の数字はひとつ目を除いた数になるので3通り、その次は2通りと、順番に減っていく場合の数の掛け合わせたものが求める場合の数になります。

組み合わせとは

本題から外れますが順列とセットで習う組み合わせについても記載します。
組み合わせとは「n個のなかからr個選ぶ」組み合わせの数です。
順列では例えば(1,2,3)と(2,1,3)は選ぶ順番が違うので別のものとカウントしますが、組み合わせでは選ばれているものが同一なので同じものとしてカウントします。
組み合わせはnCkと表記し、その計算はn!/{k!×(n-k)!}となります。

itertoolsについて

Pythonで順列や組み合わせを考えるときにitertoolsモジュールを使用するととても便利です。

itertoolsモジュールによる順列リストの作成

import itertools

nums = [1, 2, 3]  # 順列を求めるリスト

perm = itertools.permutations(nums)

print(list(perm))

# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

itertoolsモジュールをインポートします。
permutations関数を上記のように使用すると6通りすべて挙げることができました。

itertoolsモジュールによる組み合わせリストの作成

import itertools

nums = [1, 2, 3]  # 組み合わせを求めるリスト

comb = itertools.combinations(nums,2) # numsの中から2つ選ぶ組み合わせ

print(list(comb))

# [(1, 2), (1, 3), (2, 3)]

combinations関数を用いてnumsから2つ選ぶ組み合わせも簡単に求めることができました。

こんな簡単に順列や組み合わせを求めることができるなんて知りませんでした。
次回はこの内容を活かしABC183 C問題に挑戦します。