Strings Generation

Question

Hi,I would like to know how can I create various string from some given characters eg:

given characters: a, b

I would like to generate the following strings:

aa
ab
ba
bb

What I have thought of is having (for 2 inputs only) two for-loops one inside another, and then loop each to the number of inputs which in this case is 2 and the output strings will be 2*2 = 4 strings and as the number increases the number of output strings will increase by multiplying n*n (n-times)

Answer 1

I think this is a permutation question..

http://www.bearcave.com/random_hacks/permute.html

Answer 2

This is a variation of the Kleene closure (Kleene star) if that helps you in finding a solution.

Answer 3

Your approach (as much as I understood of it) sounds good as a first attempt, although the proof of the pudding is eating it, so write the code and test it :-)

Note that it won't scale very well, so the question is how many chars and how long strings you expect to be generated. If the answer is "not many", and performance / memory consumption is not an issue, it is fine to stick with the simplest solution which works. Otherwise, you need a more sophisticated algorithm.

I've had a vaguely similar task some time ago, where the number of possible permutations was so large that there was simply not enough memory to contain each at the same time. So we tried to model the permutations with numbers: note that any n long permutation of m characters can be defined with an m base number of n digits. So by iterating through all integer values from 0 until mⁿ, calling a fairly simple conversion method gets you each possible string one by one. For the index value of course you might need to use a bigger integer type like long long for bigger m and n values.

Answer 4

With recursion (just an idea demonstration):

void generate(std::string& s, size_t beg) {
  for (char c = 'a'; c <= 'b'; ++c) {
    s[beg] = c;
    if (beg < s.length() - 1) {
      generate (s, beg + 1);
    }
    else {
      std::cout << s << std::endl;
    }
  }
}

int main() {
  std::string s = "####";
  generate(s, 0);
  return 0;
}

Answer 5

You can use std::next_permutation. This will work even if you repeat letters (i.e. letters = "ababcd").

#include <algorithm>
#include <iostream>
#include <string> 


int main(int argc, char** argv) {
    std::string letters = "abcd";

    std::sort(letters.begin(), letters.end());
    do {
        std::cout << letters << "\n";
    }
    while (std::next_permutation(letters.begin(), letters.end()));
}