一个关于组合的问题?
下面代码在VC6 环境调试通过,运行结果也是正确.
我请教的问题,在最后给出.
#include <iostream>
#include <vector>
using namespace std;
template <class T>
inline void PRINT_ELEMENTS (const T& coll, char tokens[], const char* optcstr="")
{
typename T::const_iterator pos,pos1;
std::cout << optcstr;
pos=coll.begin();
pos1=0;
for (; pos != pos1; ++pos)
{
pos1 = coll.end();
pos1--;
std::cout << tokens[*pos] << ' ';
}
std::cout << std::endl;
}
//计算组合数C(n,m)
int C(int n, int m)
{
double result = 1;
for (int i = 0; i < m; i++)
{
result *= n - i;
result /= i + 1;
}
return (int)result;
}
//计算第rank个组合，rank表示序号从0到C(n,card)-1
void unrankCombination( int rank, vector<int> &subset, int card)
{
int p, m;
m = rank;
for(int i = card - 1; i >= 0; i--)
{
p = i;
while( C(p+1, i+1) <= m ) p++;
m -= C( p, i+1 );
subset[i] = p;
}
}
//计算组合的序号，从0开始，subset存放组合,（0 1 2 ... card-1 )的序号
int rankSubset( vector<int> &subset, int card)
{
int i;
int rank = 0;
for(i = 0; i < card; i++)
{
rank += C( subset[i], i + 1 );
}
return rank;
}
int main(int argc, char* argv[])
{
/*
int m = 3;
int n = 10;
*/
int m = 3;
int n = 4;
vector<int> combination( m + 1 );
/*char tokens[] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O'};*/
/*char tokens[] = {'A','B','C','D','E','F','G','H','I','J'};*/
/*char tokens[] = {'A','B','C','D','E','F','G','H','I'};*/
char tokens[] = {'A','B','C','D'};
int count = C( n, m );//组合个数,从n个数据中选择m个
for( int rank = 0; rank < count; rank++)
{
unrankCombination( rank, combination, m );
cout << rank + 1 << "-" << rankSubset( combination, m ) << ": ";
PRINT_ELEMENTS( combination, tokens );
}
cout << "\n\tpress Enter to exit ..." << endl;
cin.get();
return 0;
}
问题如下:
1)计算第rank个组合
combination是个vector ,如何理解unrankCombination( rank, combination, m );
2)计算组合的序号
如何理解 int rankSubset( vector<int> &subset, int card)
3) 如何理解rank
期待朋友的答复
[解决办法]
建议用“[code=C/C++][/code]”先排好版，要不代码稍多久看不清了
