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, Jul 31 '20 at 04:17
My rule of thumb: Take with a grain of salt any advice that starts with `#include using namespace std;` `using namespace std;` [is dangerous alone](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). Using it with `#include ` [cranks up the danger](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) 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, Jul 31 '20 at 05:17
yes it is an recursion, as we use large number of input strings, the time complexity will be less — Sourabh Misal, Jul 31 '20 at 05: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 `goto`s 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, Jul 31 '20 at 15:13
I recommend adding the desired output to the question to remove any ambiguity about your goals. — user4581301, Jul 31 '20 at 15:14
@user4581301 thanks for the insight. So does that mean its not worth it to apply complex algorithm to do such this task? The input string will go on increasing from simple {"ab", "xy"} to {"abc", "def", "ghi", "jkl", "mno", "pqr", "stu", "xyz"} where output becomes very large. — Sourabh Misal, Aug 01 '20 at 04:39
It's worth using a complex algorithm if the extra complexity reduces the work performed. For example finding an item in a `std::map` is way more complicated than finding an object in a `std::vector`, but that complexity reduces the number of iterations needed from a worst case of N to log(N). — user4581301, Aug 01 '20 at 06:05
Note that a lower Big O is not always immediately faster. A complicated solution with a lower Big O often has to perform more work per iteration to get the lower number of iterations, so for small Ns it can be outperformed by a simple solution with a worse Big O. — user4581301, Aug 02 '20 at 04:54

score 1 · Answer 1 · answered Jul 31 '20 at 05:06

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 '20 at 05:06

OrenIshShalom

5,974
9
37
87

1

Add an explanation as to how this solves the question – Arghya Sadhu Jul 31 '20 at 05:34
@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 – Sourabh Misal Jul 31 '20 at 05:51
2

@SourabhMisal Recursion does not improve the time complexity here. The shown code has the best possible complexity for the problem which you described. – eesiraed Jul 31 '20 at 06:10
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.. – Sourabh Misal Jul 31 '20 at 07:28
1

@SourabhMisal The question should be edited to indicate that any number of strings could be inputted, not just 2. – cigien Jul 31 '20 at 13:27
@SourabhMisal Recursion will not be faster. – eesiraed Jul 31 '20 at 18:27

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

1 Answers1