在探索如何创建组合的过程中,遇到了一个由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++编译了程序,程序运行得更快。