0

n 個のレベルがあり、各レベルで 2 つの可能な文字から 1 つを選択できるとします。可能なすべての文字列を出力します
。例:-
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

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 に答える
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, "");

もちろん、choices テーブルは、const-reference として渡される別のメソッド パラメータにすることもできます。これには、静的メソッドを使用する方が便利な場合があります。

--

より良い代替手段 (他の回答が 3 レベルに対して提案したものを 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 に答える