C++でサイズnの指定された配列のr要素のすべての可能な組み合わせを出力します

この問題では、サイズnと正の整数rの配列が与えられます。私たちの仕事は、サイザーの配列の要素の可能なすべての組み合わせを印刷することです。

問題を理解するために例を見てみましょう-

Input: {5,6,7,8} ; r = 3
Output : {5,6,7}, {5,6,8}, {5,7,8}, {6,7,8}

この問題を解決するためのアプローチは、要素を修正してから、他の要素を繰り返しまたはループしてすべての組み合わせを見つけることです。この場合、最初に n-r + 1を修正する必要があります 要素のみで、残りをループまたは繰り返します。

例

#include<iostream>
using namespace std;
void printRElementCombination(int arr[], int combination[], int start, int
end, int index, int r){
   if (index == r){
      cout<<"{ ";
      for (int j = 0; j < r; j++)
         cout << combination[j] << " ";
         cout<<"}\t";
      return;
   }
   for (int i = start; i <= end && end - i + 1 >= r - index; i++){
      combination[index] = arr[i];
      printRElementCombination(arr, combination, i+1, end, index+1, r);
   }
}
int main(){
   int arr[] = {1, 2, 3, 4, 5};
   int r = 3;
   int n = 5;
   int combination[r];
   cout<<"The combination is : \n";
   printRElementCombination(arr, data, 0, n-1, 0, r);
}

出力

組み合わせは-

{ 1 2 3 } { 1 2 4 } { 1 2 5 } { 1 3 4 } { 1 3 5 } { 1 4 5 }
{ 2 3 4 } { 2 3 5 } { 2 4 5 } { 3 4 5 }

同じ問題を解決する他の方法は、組み合わせに現在の要素が含まれていることを確認し、必要なサイズのすべての組み合わせを印刷することです。考え方は同じです。要素を再確認し、組み合わせをコンボ配列に格納します。ただし、要素の修正は行われません。

以下のプログラムは、問題をより理解しやすくします-

例

#include <iostream>
using namespace std;
void combinationUtil(int arr[], int n, int r, int index, int combo[], int i){
   if (index == r){
      cout<<"{";
      for (int j = 0; j < r; j++)
         cout << combo[j] << " ";
         cout<<"}\t";
         return;
   }
   if (i >= n)
      return;
   combo[index] = arr[i];
   combinationUtil(arr, n, r, index + 1, combo, i + 1);
   combinationUtil(arr, n, r, index, combo, i+1);
}
int main(){
   int arr[] = {1, 2, 3, 4, 5};
   int r = 3;
   int n = 5;
   int combo[r];
   cout<<"The combination is : \n";
   combinationUtil(arr, n, r, 0, combo, 0);
   return 0;
}

出力

組み合わせは-

{ 1 2 3 } { 1 2 4 } { 1 2 5 } { 1 3 4 } { 1 3 5 } { 1 4 5 }
{ 2 3 4 } { 2 3 5 } { 2 4 5 } { 3 4 5 }