【Python】順列・組み合わせの数と列挙する方法【Atcoder】

Atcoder

2022.05.15

この記事は約1分で読めます。

Atcoderで順列や組み合わせに関する問題の対策です。

n個のモノからr個を選んだ場合の、順列と組み合わせの数の数え方と、全通りを列挙する方法を記載しています。

自身が実装する上で必要な最低限の情報のみに絞ったため、数学的に正しくないことを書いている可能性があります。

順列

・(a,b),(b,a)のように選んだものが同じでも、並びが異なればそれぞれカウント

・nCr=n! ÷ (r!×(n-r!))

・(a,b),(b,a)のように選んだものが同じなら、並びは異なっても同じものと考える

・nCr=n! ÷ (r!×(n-r!))

from math import factorial
a = factorial(n) / factorial(r) / factorial(n - r)

1 2	from math import factorial a = factorial(n) / factorial(r) / factorial(n - r)

from math import factorial
def com(n,r):
    return (factorial(n) // (factorial(r)*factorial(n-r)))

from math import factorial

def com(n,r):

return (factorial(n) // (factorial(r)*factorial(n-r)))

for文で組み合わせの数を繰り返し計算する場合は関数化して都度呼び出すのがわかりやすいです。

from itertools import combinations
#A = [1,2,3]
#r=2
combination = list(combinations(A,r))
#print(combination)
#出力：[(1,2),(1,3),(2,3)]

from itertools import combinations

#A = [1,2,3]

#r=2

combination = list(combinations(A,r))

#print(combination)

#出力：[(1,2),(1,3),(2,3)]