組み合わせアルゴリズム: R のすべての可能な組み合わせを出力します。

組み合わせとは何ですか?

組み合わせは、特定のオブジェクトの一種の配置です。 数学用語では、組み合わせとは、アイテム/オブジェクトの固有のセットからのアイテムの選択肢/選択のセットです。 ここでは、項目の順序は関係ありません。 これは、結果の順序が重要でない、イベントの合計結果を計算する方法としても知られています。

たとえば、5 色の異なるバッグが与えられ、任意の 3 色でパターンを生成するように求められます。 3色の中から4色を選んで、順番を変えて並べることもできます。

色が RGYBI(R= 赤、G= 緑、Y= 黄、B= 青、I= 藍) であると仮定します。 したがって、考えられるパターンは RGB、RGY などです。

次の図を見てみましょう。

色の組み合わせ
色の組み合わせ

説明:

  • 4色の中から5色を選んでリストアップしてください
  • 4 色の各ブロックから、任意の 3 色を選択し、すべてリストします。 たとえば、図では「RGBI」のみを選択し、4 つの組み合わせを示しました。
  • その背後には、作成できる組み合わせの合計数を計算するための理論があります。 n 個のうちの r 個の要素の組み合わせは、数学的に次のように表すことができます。
組み合わせの公式

組み合わせの公式

記号 「!」 という意味 階乗。 例えば、
ん! = N * (N-1) * (N-2) * … * 3 * 2 * 1
言って、5! = 5*4*3*2*1 = 120

したがって、上記の問題では、n = 5 を意味する 5 つの色があり、いつでも任意の 3 つを選択する必要があります。したがって、r = 3 となります。計算すると、次のようになります。

組み合わせ

上記のシナリオでは、合計 10 色の組み合わせが可能です。

組み合わせの時間計算量分析

ここで、サイズ n の配列が与えられたとして、配列から r 個の要素を取り出し、r 個の要素の組み合わせを実行するように求められたとします。

サイズ n の配列が指定された場合、O(n2) タスクを実行する時間。 また、重複したエントリを削除したい場合は、次のようにします。

次の手順を実行する必要があります。

ステップ1) 入力配列データを昇順にソートします。ソートの時間計算量は O(n*log(n))。

ステップ2) 指定された一時配列データから一意の要素を含む別の配列を作成します。

ステップ3) 次に、組み合わせ機能を実行します。

したがって、合計時間計算量は次のようになる = オン2) + O(nLog(n))。 O(n2)、nとして2 は n*log(n) よりもはるかに大きくなります。

方法-1: 再帰を使用して要素を固定する

この方法では、要素を選択し、r-1 個の要素の組み合わせを見つけます。 残りの要素から要素を選択することは再帰的に行われるため、固定要素および再帰と呼ばれます。

図を使用してアルゴリズムを段階的に説明してみましょう。

再帰を使用した固定要素

手順は次のとおりです。

ステップ1) 最初の層では、n-r+1 個の要素を取得します。 つまり、3 つの要素を採用したということです。

ステップ2) 2 番目のレイヤーから要素を選択し、それを nr まで取り上げます。 したがって、「R」を取得すると、R を使用して G、Y、B を取得できます。

ステップ3) 3 番目の層から要素を選択し、それを n 番目の要素まで取り出し、それぞれ 3 つの要素を含むブロックを形成します。

上図は再帰の戻り値です。 最後のレイヤーのみが印刷されます。

擬似コード

function combination:
pass in: inputArray, combinationArray, start, end, index, r
if index is equal to r:
for each element in combinationArray:
print each element
return
for i = start:
if i <=end and end -i+1 > r-index:
combinationArray[index] = inputArray[i]
call combination function again with updated parameter

Cでの実装/C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int start, int end, int index, int r) {
  if (index == r) {
    for (int i = 0; i & lt; r; i++) {
      printf("%c", combinationArray[i]);
    }
    printf("\n");
    return;
  }
  for (int i = start; i & lt; = end & amp; & amp; end - i + 1 & gt; = r - index; i++) {
    combinationArray[index] = inputArray[i];
    Combination(inputArray, combinationArray, i + 1, end, index + 1, r);
  }
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, 0, n - 1, 0, r);
}

出力:

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

での実装 Python

def Combination(inputArray, combinationArray, start, end, index, r):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
i = start
while (i & lt; = end and end - i + 1 & gt; = r - index):
    combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, i + 1, end, index + 1, r)
i += 1
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [0] * r
Combination(inputArray, combinationArray, 0, n - 1, 0, r)

出力:

R G Y 
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

方法 2 (すべての要素を含めるおよび除外する)

この方法はパスカルの恒等式に基づいています。以前は nCr を計算するために再帰を使用していました。ここでは、複雑なループの代わりに単に分割されたメソッドを使用しています。

パスカルの正体によれば、

nCr = (n-1)Cr + (n-1)C(r-1)

したがって、サイズ n の指定された配列から r 要素の組み合わせを見つけるための再帰アルゴリズムには 2 つの再帰ロジックが存在します。

  1. 要素は現在の組み合わせに含まれています
  2. 要素は現在の組み合わせから除外されています

擬似コード

function combination:
pass in: inputArray, combinationArray, n, r, index, i
if the index is equal to r:
for each element in combination array:
print each element
if i>=n:
return
  combinationArray[index] = inputArray[i]
  combination(inputArray, combinationArray, n, r, index+1, i+1)
  combination(inputArray, combinationArray, n, r, index, i+1)

Cでの実装/C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int n, int r, int index, int i) {
  if (index == r) {
    for (int j = 0; j & lt; r; j++) {
      printf("%c", combinationArray[j]);
    }
    printf("\n");
    return;
  }
  if (i & gt; = n)
    return;
  combinationArray[index] = inputArray[i];
  Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
  Combination(inputArray, combinationArray, n, r, index, i + 1);
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, n, r, 0, 0);
}

出力:

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

での実装 Python

def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
if i & gt; = n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)

出力:

R G Y
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

重複する組み合わせの処理

場合によっては、入力配列に重複した要素が存在する可能性があります。

たとえば、

  • 入力配列には n = {5, 2, 3, 1, 5} が含まれています。
  • ここでは、5 が 2 回存在することがわかります。
  • ここで、この配列のコードを実行する場合、いくつかの組み合わせが繰り返されることになります。
  • {5, 2, 5}、{5, 2, 3} など、または 5 を含む任意の組み合わせが繰り返されます。

次の XNUMX つの方法を使用できます。

  • 入力配列をソートします。 ソートには O(nlog(n)) 時間がかかります。
  • 次に、i の値と i+1 の値が同じである間に、i の値を増やします。基本的に、次の XNUMX 行のコードを Combination 関数に入力します。
// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}
# for python
  while inputArray[i]==inputArray[i+1]:
    i+=1

辞書または順序なしマップを使用して重複する組み合わせを追跡する

したがって、重複を追跡するために要素を並べ替えたくない場合は、指定された手順に従うことができます。

ステップ1) グローバル ディクショナリまたはハッシュマップを宣言します。
ステップ2) 生成された Combination をハッシュマップにプッシュし、値を XNUMX つ増やします。 組み合わせがキーであり、その出現が値です。
ステップ3) 関数の実行が終了したら、ハッシュマップまたは辞書からすべてのキーを出力するだけです。

Pythonでの実装はこちら

unique_combination = dict()
def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    temp_combination = ""
for item in combinationArray:
    temp_combination += item
unique_combination[temp_combination] = unique_combination.get(temp_combination, 0) + 1
return
if i & gt; = n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBIB"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)
for item in unique_combination.keys():
    print(item)

出力:

RGY
RGB
RGI
RYB
RYI
RBI
RBB
RIB
GYB
GYI
GBI
GBB
GIB
YBI
YBB
YIB
BIB

ここでは、入力が「RGYBIB」であることがわかります。 一般に、いくつかの重複した組み合わせが発生するはずです。 ただし、辞書を使用し、各組み合わせをキーとして処理したため、一意の組み合わせのみを出力できます。

ここで、「print(unique_combination)」と書くと、それぞれの組み合わせの頻度がわかります。 次のように表示されます。

{'RGY': 1, 'RGB': 2, 'RGI': 1, 'RYB': 2, 'RYI': 1, 'RBI': 1, 'RBB': 1, 'RIB': 1, 'GYB': 2, 'GYI': 1, 'GBI': 1, 'GBB': 1, 'GIB': 1, 'YBI': 1, 'YBB': 1, 'YIB': 1, 'BIB': 1}

したがって、RGB、RYB、GYB が 2 回出現していることがわかります。辞書にキーを挿入する時間の複雑さは基本的に O(1) です。したがって、辞書を使用する場合、コードを実行する合計時間の複雑さは次のようになります。

O(1) + O(n*n)

O(n*n) に相当します。

重複を追跡する前の方法を使用すると、ソートには O(n*log(n)) が必要で、比較には O(n) が必要で、関数自体には O(n*n) かかります。合計時間の計算量は次のようになります。

O(n*log(n)) + O(n) +O(n*n)