Pythonでプログラミング-順列、組み合わせ
JavaScriptで"順列"と"組み合わせ"の説明ですがとてもわかりやすいです。
順列とは
異なる n 個のものの中から r 個取り出して並べる
順列は名前の通り"順番に並べる"というのがみそで"1,2"と"2,1"とを区別します。全ての組み合わせという方がわかりやすいかも。
組み合わせ
異なる n 個のものの中から r 個取り出す
単純な組み合わせなので順番は関係ないです。同じものであれば1つとしてカウントします。
こんな関係なので、順列と組み合わせでは順列の方がたくさんあることになります。
階乗を使ってシンプルに順列の数を求めます。階乗とは例えば"4"であれば
4 x 3 x 2 x 1 = 24 // 答えは"24"
順列のPythonでの実装です。数字"1","2","3","4"から2つの数字を選びます。
def nPr(n, r):
result = 1
for i in range(r):
result *= (n - i)
return result
print(nPr(4, 2))組み合わせの実装です。数字"1","2","3","4"から2つの数字を選びます。
def nCr(n,r):
if (r == 0) or (r == n):
return 1
return nCr(n - 1, r - 1) + nCr(n - 1, r)
print(nCr(4,2))Pythonでは公式を使って計算をすることができます。以下サイトが参考になります。
まずは順列です。数字"1","2","3","4"から2つの数字を選びます。
nが全ての数字の数、rが選ぶ数
Pythonのライブラリを使い階乗の公式"n!/(n-r)!"に当てはめます。
import math
n=4
r=2
P = (math.factorial(n))/math.factorial((n-r))
print(P)出力は"12"となります。
組み合わせは公式"n!/(n-r)!"に当てはめます。
import math
n=4
r=2
C = (math.factorial(n))/(math.factorial(r)*math.factorial((n-r)))
print(C)出力は"6"となります。
もっと簡単にズバリ順列、組み合わせのライブラリを使い方が以下で、全ての組み合わせを出力することもできる便利なものとなっています。
順列
import itertools
per = [1, 2, 3, 4, 5]
per_list = itertools.permutations(per, 2)
print(per_list)n=5、k=2の場合の順列です。これで全ての組み合わせが出力されます。
[(1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4)]
基本の形は
permutations(配列, k)
で配列の中からk個選びだします。
組み合わせ
import itertools
com = [1, 2, 3, 4, 5]
com_list = list(itertools.combinations(com, 2))
print(com_list)n=5、k=2の場合の組み合わせです。これで全ての組み合わせが出力されます。順列は並び準は関係ないため前後入れ替えたものも出力されますが組み合わせは同じ数字であれば省かれますので出力される数字は順列より少なくなります。
[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]
基本の形は
combinations(配列, k)
で配列の中からk個選びだすのは順列と同じです。
順列、組み合わせの数を出したい時は、
print(len(com_list))とlen()で数が取れます。
ライブラリを使わずにPythonで実装されているのが以下です。
参考：プログラマを育てる脳トレパズル 遊んでおぼえるPythonプログラミング＆アルゴリズム