Pythonで順列、組合せの計算をする

Pythonで順列、組合の配列を作成します。

順列

重複順列のリストを作成し個数を計算する

ユーザー定義関数による方法

まず、すべての基本となる重複順列のリストを作成します。リンゴ、ミカン、バナナの3種類のくだものを0日目、1日目、2日目の3日に分けて受け取ることを考えます。このとき、それぞれのくだもの数は十分にあり、リンゴの好きな人は3日ともリンゴを選ぶこともできます。すべての組み合わせをリストであらわすプログラムを作成します。ここでは、n種類のくだものから、r日間もらえるので、すべての組み合わせは$n^r$とおりとなります。このことも確認してみます。

重複順列　(sequence with repetition)

  1. product = [[]]
  2. r = 3
  3. n_list = ['リンゴ', 'ミカン', 'バナナ']
  4. for _ in range(r):
  5. temp = product
  6. product = []
  7. for elm in temp:
  8. for fruit in n_list:
  9. product.append(elm + [fruit])
  11. pprint.pprint(product)
  12. print(f'リストの個数:{len(product)},　nのr乗：{len(n_list)**r}')

[['リンゴ', 'リンゴ', 'リンゴ'],
 ['リンゴ', 'リンゴ', 'ミカン'],
 ['リンゴ', 'リンゴ', 'バナナ'],
 ['リンゴ', 'ミカン', 'リンゴ'],
 ['リンゴ', 'ミカン', 'ミカン'],
 ['リンゴ', 'ミカン', 'バナナ'],
 ['リンゴ', 'バナナ', 'リンゴ'],
 ['リンゴ', 'バナナ', 'ミカン'],
 ['リンゴ', 'バナナ', 'バナナ'],
 ['ミカン', 'リンゴ', 'リンゴ'],
 ['ミカン', 'リンゴ', 'ミカン'],
 ['ミカン', 'リンゴ', 'バナナ'],
 ['ミカン', 'ミカン', 'リンゴ'],
 ['ミカン', 'ミカン', 'ミカン'],
 ['ミカン', 'ミカン', 'バナナ'],
 ['ミカン', 'バナナ', 'リンゴ'],
 ['ミカン', 'バナナ', 'ミカン'],
 ['ミカン', 'バナナ', 'バナナ'],
 ['バナナ', 'リンゴ', 'リンゴ'],
 ['バナナ', 'リンゴ', 'ミカン'],
 ['バナナ', 'リンゴ', 'バナナ'],
 ['バナナ', 'ミカン', 'リンゴ'],
 ['バナナ', 'ミカン', 'ミカン'],
 ['バナナ', 'ミカン', 'バナナ'],
 ['バナナ', 'バナナ', 'リンゴ'],
 ['バナナ', 'バナナ', 'ミカン'],
 ['バナナ', 'バナナ', 'バナナ']]
リストの個数:27,　nのr乗：27

4.のforループの中で、リストsequenceにくだものを追加していきます。

5.リストsequenceを順次読みながらそのものを変更するのは難しいので、いったんsequenceを一時的にtempにコピーし、6.でsequenceを空にしてから、順次処理をしていきます。

9.でこれまで作ったリストに、さらにくだものを追加しています。

重複組み合わせは、くだものがたくさんあることを前提としているので、選択する数：rをくだものの数：3より少なくするだけでなく、多くすることもできます。また3.でn_list=range(3)とすることにより、くだものではなく0,1,2のように数字として一般化することできます。

重複組み合わせは、ギリシア文字のΠを使って次のように表現します。

重複順列　(sequence with repetition),

$\ _n\mathrm{\Pi}\ _r = n^r$

モジュールを使った重複順列の計算

itertoolsモジュールで重複順列の配列を生成する

重複順列はitertoolsモジュールを使って表示することもできます。

itertoolsモジュールによる方法

  1. import itertools
  2. list(itertools.product(['リンゴ','ミカン','バナナ'],repeat=3))
[('リンゴ', 'リンゴ', 'リンゴ'),
 ('リンゴ', 'リンゴ', 'ミカン'),
 ('リンゴ', 'リンゴ', 'バナナ'),
 ('リンゴ', 'ミカン', 'リンゴ'),
・・・(中略)
('バナナ', 'バナナ', 'ミカン'),
 ('バナナ', 'バナナ', 'バナナ')]

意味するところは#1と同じですが、1つの組み合わせはタプルになるところが相違点です。

順列のリストを作成し個数を計算する

順列のリストの作成とその個数を計算します。順列は、重複順列とは異なり、各自どのくだものも1回しか選ぶことができません。つまり、いくらリンゴが好きでも1日しか選ぶことができず、他の日はミカンとバナナを1回ずつしか選ぶことができません。数式にすると次のようになります。

順列(permutation)

考え方
$1 \leqq x_1\ne x_2\ne \cdots \ne x_k \leqq n$
順列の個数の計算
$\displaystyle {}_n\mathrm{P}_r = \frac{n!}{(n-r)!}=\overbrace {n(n-1)(n-2)・・・(n-r+1) \quad}^{r個}$

上記の式にもとづき、nこの中からr個を選ぶ順列の数を計算する関数を作成します。

順列の個数を計算する

  1. def nPr(n,r):
  2. npr=1
  3. for i in range(n,n-r,-1):
  4. npr*=i
  5. return npr
  7. nPr(3,2)
6

2.　変数nprで個数を計算します。次々と掛け算していく場合には、0ではなく1で初期化します。

3.　n,n-1・・・n-r+1まで逆にループするときには、3番目の引数は-1、また「まで」を示す2番目の引数はまでの値-1の値を指定します。この場合は(n-r+1)-1=n+rになります。

順列のリストを生成する

  1. permutation = [[]]
  2. n_list = ['リンゴ','ミカン','バナナ']
  3. r=3
  4. for _ in range(r):
  5. temp=permutation
  6. permutation=[]
  7. for elm in temp:
  8. for fruit in n_list:
  9. if fruit not in elm:
  10. permutation.append(elm + [fruit])
  12. pprint.pprint(permutation)
  13. print(f'リストの個数:{len(permutation)},　nPr：{math.factorial(len(n_list))}')
[['リンゴ', 'ミカン', 'バナナ'],
 ['リンゴ', 'バナナ', 'ミカン'],
 ['ミカン', 'リンゴ', 'バナナ'],
 ['ミカン', 'バナナ', 'リンゴ'],
 ['バナナ', 'リンゴ', 'ミカン'],
 ['バナナ', 'ミカン', 'リンゴ']]
リストの個数:6,　nPr：6

#1とほぼ同じですが、8.ですでに選ばれてリストにあるものと重複した場合には、新しいリストに入れないようにしています。

モジュールを使った順列の計算

順列にはいろいろなモジュールで個数や配列を求めることができます。

scipy.special関数による順列の数の計算

  1. from scipy.special import perm
  2. perm(3,3)
6.0

pythonのバージョンが3.8以上mathモジュールでも順列の個数を計算することができます。

mathモジュールによる順列の計算

  1. import math
  2. math.perm(5,3)
60

itertoolsで順列を生成する

itertoolsでは順列も生成することができます。

itertoolsツールによる順列の生成

  1. import itertools
  2. list(itertools.permutations(['リンゴ','ミカン','バナナ'],3))
[('リンゴ', 'ミカン', 'バナナ'),
 ('リンゴ', 'バナナ', 'ミカン'),
 ('ミカン', 'リンゴ', 'バナナ'),
 ('ミカン', 'バナナ', 'リンゴ'),
 ('バナナ', 'リンゴ', 'ミカン'),
 ('バナナ', 'ミカン', 'リンゴ')]

簡単に順列の配列を作ることができます。ここでは、個々の順列はtuppleになります。

組合せ

組み合わせの個数を計算し、配列を生成する

組み合わせは、順列に対し順序を気にしないで選ぶ方法です。数式にすると次の通りになります。

組み合わせ (combinations)

考え方
$1 \leqq x_1\lt x_2\lt \cdots \lt x_k \leqq n$
順列の個数の計算
$\displaystyle {}_n \mathrm{C}_r =\frac{_n \mathrm{P} _r}{r!}=\frac{n!}{r!(n-r)!}= \frac{\overbrace {n(n-1)(n-2)\cdots (n-r+1)}^{r個}}{\underbrace {r\times (r-1)\times \cdots 2 \times 1}_{r個}}$

組み合わせの個数を計算する

  1. def nCr(n,r):
  2. factr =1
  3. r = min(r, n-r)
  4. for i in range(r,1,-1):
  5. factr*=i
  6. return nPr(n,r)//factr
  8. nCr(3,2)
3

6.　組み合わせの個数の計算をすると、分子の個数と分母の個数が同じr個で、なおかつ分母はrから1まで連続しているので、分子のr個の中には分母の数の倍数が含まれているはずです。つまり、組み合わせの数は必ず整数になるので、//演算子を使い整数に変換します。

組み合わせの配列の生成

  1. n_list= ['リンゴ','ミカン','バナナ']
  2. combination=[[item] for item in n_list]
  3. r=2
  4. for _ in range(r-1):
  5. temp=combination
  6. combination=[]
  7. for elm in temp:
  8. for i in range(n_list.index(elm[-1])+1,len(n_list)): #+1
  9. combination.append(elm+[n_list[i]])
  11. pprint.pprint(combination)
  12. print(len(combination),nCr(len(n_list),r))
  13. print(f'リストの個数:{len(combination)},　nCr：{nCr(len(n_list),r)}')
[['リンゴ', 'ミカン'], ['リンゴ', 'バナナ'], ['ミカン', 'バナナ']]
3 3
リストの個数:3,　nCr：3

モジュールによる順列の個数の計算と配列の生成

itertoolsでは順列も生成することができます。

itertoolsによる組み合わせの生成

  1. import itertools
  2. list(itertools.combinations(['リンゴ','ミカン','バナナ','カキ'],r=3))
[('リンゴ', 'ミカン', 'バナナ'),
 ('リンゴ', 'ミカン', 'カキ'),
 ('リンゴ', 'バナナ', 'カキ'),
 ('ミカン', 'バナナ', 'カキ')]

pythonのバージョンが3.8以上mathモジュールでも順列の個数を計算することができます。

mathモジュールによる組み合わせの個数の計算

  1. import math
  2. math.perm(5,3)
6

scipyモジュールによる組み合わせの個数の計算

  1. from scipy.special import perm
  2. comb(5,3)
10.0

ictsr4 All Rights Reserved.