使用STL向量和递归实现数字排列

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

沪ICP备2024098111号-1
上海秋旦网络科技中心:上海市奉贤区金大公路8218号1幢 联系电话:17898875485