我有两个组（A）和（B）以及大量的变量abcde...（>2） 要按组排序，至少一个变量在组 （A） 中，一个变量在组 （B） 中。程序应打印出所有组合。输出的顺序并不重要。
对于 3 个变量 "abc"，结果应为：
A | B
-------
ac | b
ab | c
bc | a
a | bc
b | ac
c | ab
我写的程序是：
#include <string>
#include <stdio.h>
using namespace std;
string gencombinations(string , string );
string removeCharsFromString( string , string);
int main(){
string result;
string a = "";
string b = "";
string batch = "abc";
a = batch;
cout << "batch ta = {"; cout << a; cout << "},t batch b = {"; cout << b; cout << "}t"; cout << endl;
result = gencombinations(a, b);
//cout << result << endl;
return 0;
}
string gencombinations(string a, string b){
string _tmp;
string _tmp2;
for(int i = 0; i < a.size(); i++ ) {
_tmp = a.at(i+1);
b = _tmp+b;
cout << "remove t {"; cout << _tmp; cout << "},tt from a = {"; cout << a; cout << "}t"; cout << endl;
a= removeCharsFromString( a, _tmp );
cout << "batch ta = {"; cout << a; cout << "},t batch b = {"; cout << b; cout << "}t"; cout << endl;
if(a.size() > 1)
_tmp2 = gencombinations(a, b);
if(_tmp2 != "") return _tmp2;
b = removeCharsFromString( b, _tmp );
}
return _tmp2;
}
string removeCharsFromString( string str, string charsToRemove ) {
for (int i = 0; i < charsToRemove.length(); ++i ) {
//cout << "charsToRemove = {"; cout << charsToRemove.at(i); cout << "},t From String = {"; cout << str; cout << "}t"; cout << endl;
std::string::size_type s = str.find(charsToRemove.at(i));
if (s != std::string::npos)
str.erase(i+1, 1);
}
return str;
}
这给出了输出：
batch a = {abc}, batch b = {}
remove {b}, from a = {abc}
batch a = {ac}, batch b = {b}
remove {c}, from a = {ac}
batch a = {a}, batch b = {cb}
和休息。（一开始批次 B 中没有变量是没有问题的）。
摆脱out_of_range（@Paul的回答）我得到：
string gencombinations(string a, string b){
string _tmp;
string _tmp2;
string _resul;
for(int i = 0; i < a.size(); i++ ) {
_tmp = a.at(i);
b = _tmp+b;
if(a.size() > 1)
a= removeCharsFromString( a, _tmp );
cout << "batch ta = {"; cout << a; cout << "},t batch b = {"; cout << b; cout << "}t"; cout << endl;
if(a.size() > 1){
cout << "recursion" << endl;
_tmp2 = gencombinations(a, b);
}
if(_tmp2 != "") {
return _tmp2;
cout << "_tmp2 is empty" << endl;
}
b = removeCharsFromString( b, _tmp );
a = _tmp;
}
return _tmp2;
}
string removeCharsFromString( string str, string charsToRemove ){
for (int i = 0; i < charsToRemove.length(); ++i ) {
std::string::size_type s = str.find(charsToRemove.at(i));
if (s != std::string::npos)
str.erase(i, 1);
}
return str;
}
使用输出：
batch a = {bcd}, batch b = {a}
recursion
batch a = {cd}, batch b = {ba}
recursion
batch a = {d}, batch b = {cba}
如何正确递归？
这一行：
for(int i = 0; i < a.size(); i++ ) {
_tmp = a.at(i+1);
包含逻辑错误。字符串在 c++ 中从 0 开始，就像任何其他类型的数组或向量一样。在某些时候，代码会尝试从数组中读取字符串末尾之后的第一个字符。此时，程序将抛出一个out_of_range异常（只需用 try-catch 包装该行即可自己观看）。
至于你的代码：我不太明白tmp2的目的.代码中没有显式创建tmp2的行，因此它始终是"，与输入无关。
但实际上有更简单的解决方案，而不是在任意时间将每个字符从a移动到b，这总是会产生重复。相反，您可以使用以下简化之一：
使用 0 和 1 的排列
使用 0 和 1 的排列，其中 0 表示将字符放入 a 中，1 表示将字符放入b：
void gencombinations(string allchars){
for(unsigned int permute = 0 ; permute < (1 << allchars.size()) ; permute++){
string a, b;
for(unsigned int bit = 0 ; bit < allchars.size() ; bit++)
if(permute & (1 << bit))
a += allchars[bit];
else
b += allchars[bit];
cout << "batch: a = {" + a + "}, b: {" + b + "}" << endl;
}
}
请注意，此解决方案仅适用于特定大小的输入字符串。permute的位计数决定了输入字符串的最大长度。例如，具有 32 位的数据类型将允许最大长度为 32 的输入字符串。对于大于 64 的输入字母，需要此基本解决方案的解决方法。
使用递归调用和分发
使用递归方法调用和 fork，其中一次调用将字符添加到a，另一个添加到b：
gencombinations(string chars , string a , string b){
if(chars.size()){
char c = chars[0];
chars.erase(0 , 1);
gencombinations(chars , a + c , b);
gencombinations(chars , a , b + c);
}else
cout << "batch: a = {" + a + "}, b = {" + b + "}";
}
您不必删除任何内容。只需继续构建您的组字符串a并从批处理中b，直到批处理被释放。
当然，对于批处理中的每个字母，您必须考虑两种情况：它要么进入 A 组，要么进入 B 组。递归时，必须针对每种情况分叉递归。您还必须从批处理中删除当前字母，但这很容易，因为它是字符串中的第一个字母：
#include <string>
#include <iostream>
using namespace std;
void combo(string batch, string a, string b)
{
if (batch.size() == 0) {
if (a.size() && b.size()) {
cout << a << " :: " << b << "n";
}
} else {
combo(batch.substr(1), a + batch[0], b);
combo(batch.substr(1), a, b + batch[0]);
}
}
int main()
{
combo("abc", "", "");
return 0;
}
此解决方案仅打印递归底部的字符串。您也可以将它们附加到字符串流或字符串中。