在探索如何创建组合的过程中,遇到了一个由Hugo Steinhaus(1887年1月-1972年2月)创建的算法。他是哥廷根的David Hilbert的学生。这个算法非常简单,以至于很好奇为什么在Hugo先生之前没有人想到它。算法的基本思想是:
要创建排列,最小的数字集合是1和2。给定这两个数字,让创建所有可能的不重复的排列。结果是:
1,2
2,1
基于这个简单的矩阵,将增加其维度,使得包含排列的矩阵是一个由前一个矩阵重复组成,并以“编织”的数字索引n,从右边(最后一个索引)开始,当索引变为0时,转到下一行并重新开始。
以n=3为例,想法是(a)将每行n=3次写下来,如下所示:
1 2
1 2
1 2
2 1
2 1
2 1
...然后“编织”一个3,如下所示:
1 2 3
1 3 2
3 1 2
2 1 3
2 3 1
3 2 1
这些生成的数字可以用作可能拥有的输入数字的索引。
创建了一个名为Vector的模板类,它包含两个向量作为成员变量:一个向量用于存储结果行的数字,另一个向量用于存储结果向量(向量的向量)。这个过程包括三个步骤:
1. 设置行数大小 2. 通过创建第一个2x2矩阵来启动过程 3. 在已经创建的行中编织必要的数字
这三个步骤在类的成员函数中一一对应:
void SetMax(const unsigned int Max);
void InitProcess();
void Iterate(unsigned int iteration);
有趣的部分在于Iterate函数。这是实现Steinhaus算法的地方:
void Iterate(unsigned int iteration) {
VecVec localVec;
for (typename VecVec::iterator it = eelems.begin(); it != eelems.end(); it++) {
(*it).push_back(iteration);
size_t size = (*it).size();
for (unsigned int x = 0; x < iteration; x++) {
localVec.push_back(*it);
if (size - 1 < 1) break;
swap((*it)[size - 2], (*it)[size - 1]);
--size;
}
}
eelems = localVec;
if (iteration < max) Iterate(++iteration);
else return;
}
在过程结束时,使用静态模板函数Burp将结果发送到STDOUT,利用算法:
template
void Burp(ostream& os, vector>& vec) {
os << "Our vector of vectors" << endl;
for (typename vector>::iterator it = vec.begin(); it != vec.end(); it++) {
copy((*it).begin(), (*it).end(), ostream_iterator(os, "\n"));
os << endl;
}
os << "/Our vector of vectors" << endl;
}
对而言,向量的使用非常有趣。可以使用其他类型的数组,例如,一个int数组,但可以模板化向量,访问和修改它包含的数据的函数,以及它与使用数组一样快的事实,这使得它非常吸引人。
包含了一个Microsoft VS 2005项目,项目中也包含了(在注释中)使用g++在Cygwin上编译的命令行。
在Microsoft VS 2005上编译并在DOS窗口和Cygwin的XTERM上执行了生成的程序。相同的程序在Cygwin窗口上执行得更快!
使用g++编译了程序,程序运行得更快。