0

假设有 n 个级别，并且在每个级别中，您可以从两个可能的字符中选择一个，打印所有可能的字符串，
例如：-
假设我们有 3 个级别：-
level1 :- ab
level2 :- cd
level3 :- ef

可能的字符串是：- 1. ace
2. acf
3. ade
4. adf
5. bce
6. bcf
7. bde
8. bdf

我知道样本空间是 2^n，所以所需的时间是 O(2^n)，但我不知道如何进行编码。有哪些可能的方法以及我必须阅读哪些主题才能解决这些问题？

4

5 回答 5

5

拥有两个选项的 pow 使这很容易。把它压缩成小块。像这样的东西：

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);
}
于 2013-09-13T14:17:22.463 回答
2

在我看来，递归不是这个问题的正确答案。

你所拥有的本质上是一个三位二进制数，用 0 和 1 以外的字符表示数字。

生成所有组合包括简单地计算所有数字直到限制，然后使用这些位选择正确的字符。

这也可以概括。例如，如果您有五个级别和每个级别的六个选项，您将看到一个以 6 为底的 5 位数字（然后是每个数字可以表示的字符的 2D 集合）。

就个人而言，我不认为我会为此使用长的 if/then/else（或等效的三元运算符）。如上所述，我将使用 2D 集合，并仅索引该集合：

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";

虽然条件运算符（几乎不）可用于这种微不足道的情况，但对于任何较大版本的问题（例如，5 位、以 6 为底的版本），它们很快就会变得笨拙。

于 2013-09-13T14:44:50.400 回答
1

您似乎正在寻找的明显（并且公认丑陋）的方法使用三个嵌套循环：

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]);
        }
    }
}
于 2013-09-13T15:03:32.847 回答
0

具有任意数量级别的简单算法（也做了很多复制字符串）：

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());
    }
  }
}

像这样调用：

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

当然，选择表也可以是另一个作为常量引用传递的方法参数，如果您为此使用静态方法更方便的话。

--

一个更好的替代方案（只是对 3 个级别提出的 otehr 答案的 n 级别的概括），而不需要对递归调用进行所有复制（尽管不太容易理解）：

cout <<请注意，mystring +=如果您不直接打印，当然可以替换。

// 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'
    }
  }
}
于 2013-09-13T14:30:31.063 回答
0

您可以将 int 从 1 迭代到 pow(2, n) 并查看每个索引的二进制表示。如果该位为 0，则使用左侧，如果该位为 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;
}

输出：

aceg
aceh
acfg
acfh
adeg
adeh
adfg
adfh
bceg
bceh
bcfg
bcfh
bdeg
bdeh
bdfg
bdfh
于 2013-09-13T20:13:30.033 回答