重複のある順列／重複のない順列／組み合わせを列挙するアルゴリズムをExcelで

2023年10月13日

◆仕事や勉強の息抜きに。。。

順列／組み合わせを使うケース

重複のある順列（ケース１）

ある物流センターでは4つの工程があり、それぞれの工程に7社、合計で28社の派遣業者がいます。

派遣業者の組み合わせは何通りでしょうか？

 

重複のない順列（ケース２）

ある物流センターでは4つの工程があり、全体で7社の派遣業者がいて、各社ともすべての工程を請け負うことができますが、一度に複数の工程は請け負えません。

派遣業者の組み合わせは何通りでしょうか？

 

組み合わせ（ケース３）

ある物流センターには7社の派遣業者がいますが、毎日4社までしか起用しません。

派遣業者の組み合わせは何通りでしょうか？

 

順列／組み合わせの数を求める計算式

重複のある順列（ケース１）

各工程で7通りの業者を選べますので、

1工程しかない場合・・・7通り

2工程しかない場合・・・7×7通り

3工程しかない場合・・・7×7×7通り

4工程の場合・・・7×7×7×7＝2,401通り

となります。

これは重複のある順列と呼ばれ、このように累乗で計算できるのか特徴です。

 

重複のない順列（ケース２）

7社の派遣業者はすべての工程を請け負うことができますが、重複は許されません。

そのため、業者Aが工程1を請け負ったら、工程2を請け負える業者は6社に絞られます。

同様に、工程3は5社、工程4は4社に絞られます。

従って、業者の組み合わせは7×6×5×4＝840通りです。

これは通常の順列の公式でも解けます。

 

n個からk個を選ぶ順列の数は、

n! / (n-k)!

>> 順列と組み合わせ

 

組み合わせ（ケース３）

今度は工程の区別がないため、

業者A＋業者B＋業者C＋業者D

の組み合わせと、

業者B＋業者A＋業者C＋業者D

の組み合わせは同一です。

従って、組み合わせの数を計算する公式で解けます。

 

n個からk個を選ぶ組み合わせの数は、

n! / (n-k)!k!

>> 順列と組み合わせ

 

この公式に当てはめると、

7!/(7-4)!3! = 35通りになります。

 

順列／組み合わせをExcelで列挙するアルゴリズム

ケース1・・・2,401通り

ケース2・・・840通り

ケース3・・・35通り

となりましたが、すべてのパターンを列挙するにはどのようにすれば良いでしょうか？

ケース3はともかく、他の2つは手計算では難しそうです。

 

このような時に役立つのが、エクセルVBAです。

まずはケース1からやってみましょう。

 

重複のある順列（ケース１）

これは4ケタの4つの数字一つずつを、1から1つずつ増やしていけば良いので簡単です。

1111から始まって、末尾のケタを1ずつ増やしていき、7まで行ったら1に戻し、前のケタを1増やします。

 

この操作を延々と続けて、エクセルのシートに行を変えて書き込んでいけば求まります。

このような操作をマクロにさせるには、For～Next文を使います。

>> 【算術計算】物流シミュレーションに必要な機能はたったこれだけ！最短距離でマクロを使えるようにします！

 

サンプル文は次の通りです。

XX = 1
For a1 = 1 To 7
　For a2 = 1 To 7
　　For a3 = 1 To 7
　　　For a4 = 1 To 7
　　　　XX = XX + 1
　　　　CBN = a1 & a2 & a3 & a4
　　　　Range(Cells(XX, 1), Cells(XX, 1)) = CBN
　　　Next a4
　　Next a3
　Next a2
Next a1

 

変数a1を一桁目、a2を二桁目、a3を三桁目、a4を4桁目としています。

これらを入れ子構造のFor～Next文とすることによって、四桁目から一桁目に遡って1～7に変化させます。

 

XXは行数を一つずつ増やすための変数です。

最初は1にしておいて、For～Next文でa1～a4の数字が1ずつ変わるたびに1ずつ増加させます。

これにより、前に書き込んだ数字が上書きされずに次の数字が書き込めます。

 

CBN = a1 & a2 & a3 & a4では、a1からa4の数字を1つの文字列に合体させて、CBNという新しい変数に入れています。

そして、Range(Cells(XX, 1), Cells(XX, 1)) = CBNで、シートの1列目に行を一つずつ下げながら書き込んでいます。

 

重複のない順列（ケース２）

ケース1で書き込んだ2,401通りの数字は、2211や4556のように各桁の数字が重複しているものも含まれています。

これらの重複を見つけて削除していきます。

やり方はいろいろありますが、一つのやり方は次の通りです。

 

  1. a1からa4を変化させ、4ケタの数字を生成してB2セルからE2セルに書き込む
  2. 1の数字を昇順に並べ替える
  3. 隣り合う数字同士をチェックし、同じ数字があれば却下して1に戻る
  4. 隣り合う数字がすべて異なれば、シートのA列にある数字をすべてチェックし、同じ4ケタの数字がないかチェックする。あれば却下し1に戻る
  5. A列に同じ数字がなければ、A列の最終行に4ケタの数字を書き込む

 

イラストで描くと次のようになります。

 

サンプルプログラムは以下のようになります。

XX = 1
For a1 = 1 To 7
　For a2 = 1 To 7
　　For a3 = 1 To 7
　　　For a4 = 1 To 7
　　　　Range(Cells(2, 2), Cells(2, 2)) = a1
　　　　Range(Cells(2, 3), Cells(2, 3)) = a2
　　　　Range(Cells(2, 4), Cells(2, 4)) = a3
　　　　Range(Cells(2, 5), Cells(2, 5)) = a4

　　　　With ActiveSheet
　　　　　.Sort.SortFields.Clear
　　　　　.Sort.SortFields.Add Key:=.Range(Cells(2, 2), Cells(2, 5)), Order:=xlAscending
　　　　　.Sort.SetRange .Range(Cells(2, 2), Cells(2, 5))
　　　　　.Sort.Orientation = xlSortRows
　　　　　.Sort.Apply
　　　　End With

　　　　aa1 = Range(Cells(2, 2), Cells(2, 2))
　　　　aa2 = Range(Cells(2, 3), Cells(2, 3))
　　　　aa3 = Range(Cells(2, 4), Cells(2, 4))
　　　　aa4 = Range(Cells(2, 5), Cells(2, 5))

　　　　SS = 0
　　　　If aa1 = aa2 Then
　　　　　SS = 1
　　　　ElseIf aa2 = aa3 Then
　　　　　SS = 1
　　　　ElseIf aa3 = aa4 Then
　　　　　SS = 1
　　　　Else
　　　　　SS = 0
　　　　End If

　　　　If SS = 0 Then
　　　　　XX = XX + 1
　　　　　CBN = a1 & a2 & a3 & a4
　　　　　Range(Cells(XX, 1), Cells(XX, 1)) = CBN
　　　　End If

　　　Next a4
　　Next a3
　Next a2
Next a1

 

With～End Withの部分で4ケタの各桁を昇順に並べ替えています。

マクロでのソートの仕方はネット上に沢山載っているので、詳しくはそちらを参照して下さい。

 

隣り合うケタ同士の数字が違う場合にはシートのA列に書き込んでいきますが、新しく書き込む前に同じ4ケタの数字がないかをSS=0～End Ifの部分でチェックしています。

 

結果はこのようにA列に書き込まれます。

 

組み合わせ（ケース３）

ケース2で書き出した840通りの数字は、1235や2351などのように同じ数字の組み合わせが含まれています。

これらの同じ組み合わせの数字を削除していきます。

 

これはケース2のプログラムを少し変更するだけでできます。

ケース2では昇順に並べ替えて隣り合う数字同士をチェックした後、元の数字をA列に書き込みましたが、代わりに昇順に並べ替えた数字をA列に書き込むだけです。

 

サンプルプログラムは次のようになります。

XX = 1
For a1 = 1 To 7
　For a2 = 1 To 7
　　For a3 = 1 To 7
　　　For a4 = 1 To 7
　　　　Range(Cells(2, 2), Cells(2, 2)) = a1
　　　　Range(Cells(2, 3), Cells(2, 3)) = a2
　　　　Range(Cells(2, 4), Cells(2, 4)) = a3
　　　　Range(Cells(2, 5), Cells(2, 5)) = a4
　　　　With ActiveSheet
　　　　　.Sort.SortFields.Clear
　　　　　.Sort.SortFields.Add Key:=.Range(Cells(2, 2), Cells(2, 5)), Order:=xlAscending
　　　　　.Sort.SetRange .Range(Cells(2, 2), Cells(2, 5))
　　　　　.Sort.Orientation = xlSortRows
　　　　　.Sort.Apply
　　　　End With
　　　　aa1 = Range(Cells(2, 2), Cells(2, 2))
　　　　aa2 = Range(Cells(2, 3), Cells(2, 3))
　　　　aa3 = Range(Cells(2, 4), Cells(2, 4))
　　　　aa4 = Range(Cells(2, 5), Cells(2, 5))

　　　　SS = 0
　　　　If aa1 = aa2 Then
　　　　　SS = 1
　　　　ElseIf aa2 = aa3 Then
　　　　　SS = 1
　　　　ElseIf aa3 = aa4 Then
　　　　　SS = 1
　　　　Else
　　　　　SS = 0
　　　　End If

　　　　If SS = 0 Then
　　　　　CBN = aa1 & aa2 & aa3 & aa4
　　　　　For I = 1 To XX
　　　　　　If Range(Cells(I, 1), Cells(I, 1)) = CBN Then
　　　　　　　SS = 1
　　　　　　Else
　　　　　　End If
　　　　　Next I
　　　　End If

　　　　If SS = 0 Then
　　　　　XX = XX + 1
　　　　　CBN = aa1 & aa2 & aa3 & aa4
　　　　　Range(Cells(XX, 1), Cells(XX, 1)) = CBN
　　　　End If

　　　Next a4
　　Next a3
　Next a2
Next a1

 

変えたのはIf SS=0 Then～End Ifの箇所だけです。

結果はこのようにA列に書き込まれます。

 

まとめ

順列や組み合わせの数を計算するのは。公式を使えば簡単にできます。

しかし、それらの数字をすべて列挙するのは、nが大きくなると人手では困難です。

そのような場合に、エクセルVBAを使えば比較的簡単にモレなく列挙させることができます。

For～Next文がすべてのパターンを虱潰しにチェックするのに役立ちます。

 

このようにしてすべてのパターンを書き出すことによって、二項定理や多項定理を使って所望の確率を計算できるようになりますので、実務でも有用です。

 

順列順列組合せ

Posted by ロジギーク