Generate Possible combinations of two given strings in c++ using recursion

Question

I am trying to figure out how to print all the combinations in c++. Given input is {"abc","xyz"} and desired output is {"ax", "ay", "az", "bx", "by", "bz", "cx", "cy","cz"} I found this recursion code snippet :

`#include <bits/stdc++.h>
 using namespace std;
 void printKLengthString(char set[], string sequence, int n, int k) {
   if (k == 0){
      cout<<sequence<<"\t";
      return;
   }
   for (int i = 0; i < n; i++){
      string newSequence;
      newSequence=sequence+set[i];
      printKLengthString(set, newSequence, n, k - 1);
   }
 }
 int main() {
    char set[] = {'a', 'b'};
    int n = 2;
    int k = 3;
    printKLengthString(set, "", n, k);
 }`

but I am not able to manipulate it according to my desired inputs

Update 1: Here is my code:

    `#include <bits/stdc++.h>
using namespace std;
void printKLengthString(vector<char> set, string sequence, int n, int k) {
   if (k == 0){
      cout<<sequence<<"\t";
      return;
   }
   for (int i = 0; i < n; i++){
      string newSequence;
      newSequence=sequence+set.at(i);
      printKLengthString(set, newSequence, n, k - 1);
   }
}
int main() {
   vector<string> stringIn = {"ab", "xy"};
   // int n = 2;
   // int k = 2;
   // for (int i = 0; i < set.size(); i++) {
   //   cout << set[i] << "\n";
   // }
   vector<char> set;

   for (int i = 0; i < stringIn.size(); i++) {
        for (int j = 0; j < stringIn[0].size(); j++) {
         // cout << stringIn[i].at(j) << "\n";
         // str += char(set[i].at(j));
         set.push_back(stringIn[i].at(j));
         
        }
   }
   // for (char k: set) {
   //   cout << k << "\t";
   // }
    cout << "\n";
   // cout << "stringIn Size : " << stringIn.size() << "\n"; 
   // cout << "set Size : " << set.size() << "\n";

   int k = stringIn.size();
   int n = set.size();
   printKLengthString(set, "", n, k);
}`

I am getting output as :

aa ab ax ay ba bb bx by xa xb xx xy ya yb yx yy
which is permutation but I just want the combination , which I am not able to figure out..

Anyone could guide me?

Update 2: I want to scale this for multiple inputs, e.g. {"abc","def","ghi","xyz"}

Is it an obligation to use recursion ? Because 2 for loop is enough for you desired output — thibsc
– thibsc, Commented Jul 31, 2020 at 4:17
My rule of thumb: Take with a grain of salt any advice that starts with #include <bits/stdc++.h> using namespace std; using namespace std; is dangerous alone. Using it with #include <bits/stdc++.h> cranks up the danger by cramming the entire C++ Standard library into your program. With tens of thousands of unnecessary identifiers now in the global namespace you're coding in a minefield. — user4581301
– user4581301, Commented Jul 31, 2020 at 5:17
yes it is an recursion, as we use large number of input strings, the time complexity will be less — Sourabh Misal
– Sourabh Misal, Commented Jul 31, 2020 at 5:44
Time complexity is a measurement of number of operations performed. It does not care if you perform the operations because of loop iterations, recursion. You can throw gotos into the mix, manually perform loop unrolling, and overly complicate the code to conceal the true number of iterations and that won't change the time complexity. To reduce time complexity you must change the algorithm to reduce the amount of work performed. — user4581301
– user4581301, Commented Jul 31, 2020 at 15:13
I recommend adding the desired output to the question to remove any ambiguity about your goals. — user4581301
– user4581301, Commented Jul 31, 2020 at 15:14

OrenIshShalom · Accepted Answer · 2020-07-31 05:06:59Z

1

const unsigned int n1 = strlen(s1);
const unsigned int n2 = strlen(s2);
for (unsigned int i1=0;i1<n1;i1++)
{
    for (unsigned int i2=0;i2<n2;i2++)
    {
        printf("%c%c\n",s1[i1],s2[i2]);
    }
}

answered Jul 31, 2020 at 5:06

OrenIshShalom

7,3109 gold badges54 silver badges141 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Arghya Sadhu Over a year ago

Add an explanation as to how this solves the question

Sourabh Misal Over a year ago

@OrlenshShalom , the output is according to the requirements, but when many string inputs are used, the time complexity factor comes in.. Hence the need to use recursion

user9254539 Over a year ago

@SourabhMisal Recursion does not improve the time complexity here. The shown code has the best possible complexity for the problem which you described.

Sourabh Misal Over a year ago

Yes @BessieTheCow, for the example input I gave, it is absolutely correct. I want to scale my inputs from 2 to 100, which takes a lot to time, hence, I am asking for a method using recursion or any other method faster than this..

cigien Over a year ago

@SourabhMisal The question should be edited to indicate that any number of strings could be inputted, not just 2.

|

Collectives™ on Stack Overflow

Generate Possible combinations of two given strings in c++ using recursion

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related