Print all strings, O(2^n) algorithm

Question

Suppose there are n levels and in each levels you can choose one out of two possible characters, Print all possible strings
eg:-
Suppose We have 3 levels:-
level1 :- a b
level2 :- c d
level3 :- e f

possible strings are:- 1. ace
2. acf
3. ade
4. adf
5. bce
6. bcf
7. bde
8. bdf

I know that the sample space is 2^n so the time required is O(2^n), but I can't figure out how can I go about coding it. What could be possible approches and what topics do I have to read to solve such problems?

Recursion seems the way to go. In general, you have that, given a level n and a prefix, the set of strings you can generate with said prefix is prefix + all the substrings you can generate from that level on. — Save, Sep 13 '13 at 14:11
Search for "Cartesian product" here on SO or your favorite search engine. For example: [Cartesian product of several vectors](http://stackoverflow.com/questions/2405242/cartesian-product-of-several-vectors) or [How can I create cartesian product of vector of vectors?](http://stackoverflow.com/questions/5279051/how-can-i-create-cartesian-product-of-vector-of-vectors) — Blastfurnace, Sep 13 '13 at 14:29

score 5 · Accepted Answer · answered Sep 13 '13 at 14:17

5

Having a pow-of-two number of choices makes this easy. Condence it into bits. Something like this:

char buf[3];
for(unsigned i = 0; i < 10; ++i)
{
    buf[0] = i & 4 ? 'b' : 'a';
    buf[1] = i & 2 ? 'd' : 'c';
    buf[2] = i & 1 ? 'f' : 'e';

    std::string str = std::string(buf, 3);
}

answered Sep 13 '13 at 14:17

Cory Nelson

29,236
5
72
110

2

Note that `2*2*2 != 10` – Jarod42 Sep 13 '13 at 14:25
Thanks it Works fine, only the number of iterations should 2^levels, – Hidetoshi Sep 13 '13 at 14:37
Thanks I easily generalized it for n levels! But can you please elaborate how its working! – Hidetoshi Sep 14 '13 at 08:04

score 2 · Answer 2 · answered Sep 13 '13 at 14:44

In my opinion, recursion is not the right answer for this.

What you have is essentially a three-digit binary number, with characters other than 0 and 1 to represent the digits.

Generating all the combinations consists of simply counting through all the numbers up to the limit, then using the bits to choose the correct characters.

This can also be generalized. For example, if you had five levels and six choices at each level, you'd be looking at a 5 digit number in base 6 (and then a 2D collection of the characters each digit can represent).

Personally, I don't think I'd use a long if/then/else (or, equivalently, ternary operators) for this. As suggested above, I'd use a 2D collection, and just index into that collection:

char const *names [] = { "ab", "cd", "ef" };

for (unsigned i = 0; i < 8; i++) 
    std::cout << names[0][i >> 0 & 1]
              << names[1][i >> 1 & 1]
              << names[2][i >> 2 & 1]
              << "\n";

While conditional operators are (barely) usable for a case this trivial, for any larger version of the problem (e.g., the 5-digit, base-6 version), they quickly become unwieldy.

+1 for the LUT. I considered it but ended up using branches because I think they convey the general idea a bit better. Would definitely recommend using a LUT if there are more than two possibilities. — Cory Nelson, Sep 13 '13 at 15:05

score 1 · Answer 3 · answered Sep 13 '13 at 15:03

1

The obvious (and admittedly ugly) method you seem to be looking for uses three nested loops:

char level1[] = "ab";
char level2[] = "cd";
char level3[] = "ef";

int x, y, z;

for (x = 0; x < 2; ++x)
{
    for (y = 0; y < 2; ++y)
    {
        for (z = 0; z < 2; ++z)
        {
            printf("%c%c%c\n", level1[x], level2[y], level3[z]);
        }
    }
}

answered Sep 13 '13 at 15:03

Jim Mischel

131,090
20
188
351

Yeah, but then you don't know the number of levels at the beginning, its just a case when no. of levels=3 – Hidetoshi Sep 13 '13 at 15:33
@Hidetoshi: Yes, that's true. The other answers show how to simulate multiple loops (with recursion, for example), or use a single loop with some clever math. – Jim Mischel Sep 13 '13 at 15:42

b.buchhold · Answer 4 · 2013-09-13T15:08:36.037

The trivial algorithm with an arbitrary number of levels (also does a lot of copying strings):

class StringCombinations {
  public:
  // filled somehow
  std::vector<std::pair<char, char> > choices;

  void printStrings(size_t level, std::string prefix) {
    assert(level < choices.size());
    if (level == choices.size() - 1) {
      cout << prefix << choices[i].first();
      cout << prefix << choices[i].second();
    } else {
      printStrings(level +1, prefix + choices[i].first());
      printStrings(level +1, prefix + choices[i].second());
    }
  }
}

called like this:

StringCombinations sc;
// Set the choices table somehow.
...
sc.printStrings(0, "");

the choices table could, of course, also be another method parameter that is passed as const-reference, if it is more convenient for you to have a static method for this.

--

A better alternative (just the generalization to n levels of what otehr answers proposed for 3 levels) without all that copying for the recursive calls (less understandable, though):

Note that you can, of course, repalce cout << with mystring += if you do not print directly.

// all strings have size 2, 0'th char and 1'st char correspond to the choices 
std::vector<std::string> choices;

void printStrings() {
  for (size_t i = 0; i < static_cast<size_t>(pow(2, choices.size())); ++i) {
    for (size_t j = 0; j < choices.size(); ++j) {
      // Checks the bit in i (from the right) that fits the current level (j).
      cout << choices[j][i & (j << x)];
      // 2^#levels different values of i, ensure as many different outcomes
      // (disregarding trivial choices between, e.g., 'a' and 'a'
    }
  }
}

score 0 · Answer 5 · answered Sep 13 '13 at 20:13

You can iterate an int from 1 to pow(2, n) and look at the binary representation of each index. Use the left if the bit is 0, the right if the bit is 1:

void PrintDigits(char **str, int size, int val)
{
    char *tmp = new char[size + 1];
    assert(tmp);

    tmp[size] = '\0';
    while (size) {
        tmp[size - 1] = str[size - 1][val % 2];
        val = val >> 1;
        size --;
    }

    printf("%s\n", tmp);
}

int main(int argc, char *argv[])
{
    char *str[] = {"ab", "cd", "ef", "gh"};

    int len = sizeof(str) / sizeof(str[0]);

    for (int i = 0; i < (1 << len); i++) {
        PrintDigits(str, len, i);
    }

    return 0;
}

Output:

aceg
aceh
acfg
acfh
adeg
adeh
adfg
adfh
bceg
bceh
bcfg
bcfh
bdeg
bdeh
bdfg
bdfh

Print all strings, O(2^n) algorithm

5 Answers5