0

ありがとう@Scotty、@paddy。参考までに、最適なソリューションは次のとおりです。

void RecSubsets(string soFar, string rest) {
    if (rest == "") {
        cout << soFar << end;
    }
    else {
      RecSubsets(soFar + rest[0], rest.substr(1));
      RecSubsets(soFar, rest.substr(1));
    }
 }

void CanMakeSum(string set) {
    RecSubsets("", set);
 }

データを 2 つのセット (C(n-1, k-1) & C(n-1, k)) に分割し、関数を再帰的に呼び出すことにより、セット内のすべての可能な組み合わせを計算する簡単なプログラムを作成しています。以下は私が書いたものです：

void RecSubsets(string soFar, string rest) {
    if (rest == "") cout << soFar << end;
    }
    else {
        for (int i = 0; i < rest.length(); i++) {
            string next = soFar + rest[i];
            string remaining = rest.substr(i+1);
            RecSubsets(next, remaining);
        }
    }
}

void CanMakeSum(string set) {
    RecSubsets("", set);
    RecSubsets("", set.substr(1));
}

int main() {    
    string set = "abcd";
    CanMakeSum(set);
    return 0;
}

したがって、「abcd」の入力文字列の場合、2 つのグループ (abcd と abc) に分割され、関数を再帰的に呼び出して組み合わせを出力します。このロジックでは、出力は abcd、abc、abd、ab、acd、ac、ad、a... のはずですが、上記のプログラムを使用すると、出力は abcd、abd、acd、ad... となります。概念的には私が達成しようとしていることですが、それをコードに変換するのは困難です。誰かが私が間違っているところを指摘できますか? ありがとう

4

2 に答える 2

0

事前注文ではなく、事後注文で結果を印刷したい。他の答えはほぼ正しいですが、あなたはそれを簡単に却下しました。文字列の並べ替えがないため、順列を行っていません。

必要な順序でデータを出力する正しいコードは次のとおりです。

void RecSubsets(string soFar, string rest) {
    for (int i = 0; i < rest.length(); i++) {
        string next = soFar + rest[i];
        string remaining = rest.substr(i+1);
        RecSubsets(next, remaining);
    }
    if( soFar.size() > 0 ) cout << soFar << endl;
}

出力：

abcd
abc
abd
ab
acd
ac
ad
a
bcd
bc
bd
b
cd
c
d
bcd
bc
bd
b
cd
c
d
于 2012-09-07T02:55:32.027 に答える
0

いい試みです。小さな問題が 2 つあります。

  1. 「データを 2 つのセット (C(n-1, k-1) & C(n-1, k)) に分割する」べきではありません。それがあなたの再帰関数の目的です！

  2. RecSubsets()常に印刷する必要がありますsoFar。を取り外しますif (rest == "")。

例えば：

void RecSubsets(string soFar, string rest) {
    // First print out "a" or wherever we are up to
    // This ensures we correctly get "ab" and "ac" without trailing characters etc
    cout << soFar << end;

    // Now print out the other combinations that begin with soFar
    // This part of your algorithm was already correct :)
    for (int i = 0; i < rest.length(); i++) {
        string next = soFar + rest[i];
        string remaining = rest.substr(i+1);
        RecSubsets(next, remaining);
    }
}

void CanMakeSum(string set)
{
    RecSubsets("", set);
    // Don't call it a second time here
}
于 2012-09-07T00:46:07.203 に答える