计算一个数的所有组合数 代码(C++)
本文地址: http://blog.csdn.net/caroline_wendy
计算一个数的组合数, 使用递归进行求解.
如果计算3位的组合数, 首先任选固定一位, 然后计算其余两位的组合数, 最后组合至一起. 如 1 + [23, 32] = 123, 132;
在固定其余位数, 如 2 + [13, 31] = 213, 231; 3 + [12, 21] = 312, 321;
程序分为两步分, 一个删除任意位置的一个元素, 一个是递归求解组合数.
代码:
/*
* Combination.cpp
*
* Created on: 2014.6.9
* Author: Spike
*/
/*eclipse cdt, gcc 4.8.1*/
#include <iostream>
#include <vector>
#include <string>
using namespace std;
void deleteOneNum (std::string& _num, std::size_t _n) {
if (_n >= _num.length()) {
return;
}
string temp (_num.substr(_n+1));
_num = _num.substr(0, _n) + temp;
}
void combination (std::string _num, std::string _buff,
std::vector<std::string>& _result)
{
if (_num.length() <= 0) {
_result.push_back(_buff);
}
for (std::size_t i=0; i<_num.length(); ++i) {
std::string temp (_num);
deleteOneNum(temp, i);
combination(temp, _buff+_num[i], _result);
}
}
int main (void) {
std::string num("4123");
std::vector<std::string> result;
combination(num, "", result);
for (std::size_t i=0; i<result.size(); ++i) {
std::cout << result[i] << std::endl;
}
return 0;
}
输出:
4123 4132 4213 4231 4312 4321 1423 1432 1243 1234 1342 1324 2413 2431 2143 2134 2341 2314 3412 3421 3142 3124 3241 3214