C++で再帰を使って単語リストの組み合わせから作れるすべての文を出力する方法

単語リストが与えられたとき、再帰的なアプローチを用いて各リストから1つずつ単語を選び、生成できるすべての文の組み合わせを出力することを目標とします。各リストから一度に選べる単語は1つだけというルールです。

入出力シナリオの確認

例1

入力 −

sentence[row][col] = {{"I", "You"},
   {"Do", "do not like"},
   {"walking", "eating"}}

出力 −

I Do walking
I Do eating
I like walking
I like eating
You Do walking
You Do eating
You like walking
You like eating

説明 − sentence[0]〜sentence[2] の各行から1つずつ単語を選ぶことで、上記のようなすべての文が生成されます。

例2

入力 −

sentence[row][col] = {{"work", "live"},{"easy", "happily"}}

出力 −

work easy
work happily
live easy
live happily

説明 − sentence[0]〜sentence[1] の各行から1つずつ単語を選ぶことで、上記のようなすべての文が生成されます。

アルゴリズムの手順

• 文字列型の2次元配列 sentence[row][col] を宣言し、そのデータを関数 Recursive_Print(sentence) に渡します。
• 関数 Recursive_Print(sentence) の内部では以下を行います。
  • 文字列型の配列 arr[row] を作成します。
  • i を 0 から col 未満までループさせます。ループ内で sentence[0][i] が空でない場合、関数 Recursion(sentence, 0, i, arr) を呼び出します。
• 関数 Recursion(string sentence[row][col], int temp_1, int temp_2, string arr[row]) の内部では以下を行います。
  • arr[temp_1] に sentence[temp_1][temp_2] を代入します。
  • temp_1 が row - 1 と等しい場合、i を 0 から row 未満までループさせ、ループ内で arr[i] を出力します。
  • i を 0 から col 未満までループさせます。ループ内で sentence[temp_1+1][i] が空文字列と等しくない場合、関数 Recursion(sentence, temp_1+1, i, arr) を再帰的に呼び出します。
• 結果を出力します。

プログラムで使用しているアプローチ

このプログラムでは、まず最初の行の各単語について再帰呼び出しを開始します。再帰関数は現在の行の単語を一時配列に保存し、最終行に到達した時点でそれまでに蓄積した単語を連結して1つの文として出力します。まだ最終行に達していない場合は、次の行の各単語に対して自分自身を再帰的に呼び出すことで、すべての組み合わせを網羅的に探索します。

コード例

#include<bits/stdc++.h>
#define row 3
#define col 3
using namespace std;
void Recursion(string sentence[row][col], int temp_1, int temp_2, string arr[row]){
   arr[temp_1] = sentence[temp_1][temp_2];
   if(temp_1 == row - 1){
      for(int i=0; i < row; i++){
         cout << arr[i] << " ";
      }
      cout << endl;
      return;
   }
   for(int i=0; i < col; i++){
      if(sentence[temp_1+1][i] != ""){
         Recursion(sentence, temp_1+1, i, arr);
      }
   }
}
void Recursive_Print(string sentence[row][col]){
   string arr[row];
   for(int i=0; i < col; i++){
      if(sentence[0][i] != ""){
         Recursion(sentence, 0, i, arr);
      }
   }
}
int main(){
   string sentence[row][col] = {{"Ajay", "sanjay"},{"Like", "is"},{"Reading", "eating"}};
   Recursive_Print(sentence);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます。

Ajay Like Reading
Ajay Like eating
Ajay is Reading
Ajay is eating
sanjay Like Reading
sanjay Like eating
sanjay is Reading
sanjay is eating