遞歸 - 子集 - C++

謝謝@Scotty，@paddy。僅供參考，最優解是這樣的：遞歸 - 子集 - C++

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，... 但是，使用上面的程序，輸出是abcd，abd，acd，ad ... 我在概念上理解我想要達到的目標，但難以將其轉化爲代碼。有人可以指出我要去哪裏嗎？謝謝

來源

2012-09-07 Rex F

試圖在調試跟蹤呢？ –

這是一個很好的嘗試。只是有兩個小問題：

你應該不是「分裂的數據分成兩組（C（N-1，K-1）& C（N-1，K））」。這就是你的遞歸功能！
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-07 00:46:07 Scotty

感謝您的回覆。你所建議的是遞歸排列算法。我已經做到了，理解它（但是我做了與你相反的事情 - 從左到右 - 因此'if rest ='「'）。但在這裏，我特別希望它使用子集方法來實現，這意味着第一級分爲2組 - （a，bcd）和（「」，bcd）。然後遞歸地調用函數。 –

對不起，我不明白你的問題。事實上，我仍然不明白你的意思。你在尋找兩套交叉口嗎？你能指定你需要的確切輸出嗎？ – Scotty

感謝Scotty，@paddy。僅供參考，我期待的最佳解決方案是： –

你想打印後的順序，而不是預先訂購的結果。另一個答案几乎是正確的，但你太容易解散了。它沒有進行排列，因爲沒有對字符串進行重新排序。

正確的代碼輸出在您需要的順序中的數據是這樣的：

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-07 02:55:32 paddy

遞歸 - 子集 - C++

回答

相關問題