使用 STL 向量和递归（ 使用 Steinhaus 算法） 进行排列

• 下载源码 - 5.09 KB

引言

这是一个使用STL向量和递归生成无重复数字排列组合的命名空间，包含类和函数。 

在研究如何创建组合（参见我之前的文章）时，我遇到了由Hugo Steinhaus（1887年1月-1972年2月）创建的算法（这里），他是哥廷根的 David Hilbert 的学生。 

背景 

这段代码是我为了学习STL而进行的几个练习之一。

事实上，这个算法非常简单，我不知道为什么在 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. 通过创建我们的第一个 2 x 2 矩阵来启动该过程
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;
    }

 在过程结束时，我们使用 static 模板函数 Burp 将结果发送到 STDOUT 生成的向量的向量，利用一个算法：  

// displays results after processing is done
template <typename T>
void Burp(ostream& os, vector< vector<T> >& vec)
    {
    os << "Our vector of vectors" << endl;
    for(typename vector< vector<T> >::iterator it = vec.begin(); it!= vec.end();it++)
        {
        copy((*it).begin(), (*it).end(), ostream_iterator<unsigned int>(os, " "));
        os << endl;
        }
    os << "/Our vector of vectors" << endl;
    }

关注点

向量的使用对我来说很有趣。 我可以使用其他类型的数组，例如，一个 int 数组，但我们可以对向量进行模板化，访问和修改它包含的数据的函数，而且它与使用数组一样快，这对我很有吸引力。

我包含了一个 Microsoft VS 2005 项目，其中还包含（在注释中）使用 g++ 在 Cygwin 上编译它的命令行。 

结论

我在 Microsoft VS 2005 上编译并在 DOS 窗口和 Cygwin 上的 XTERM 上执行了生成的程序。 相同的程序在 Cygwin 窗口上执行得更快！
我使用 g++ 编译了该程序，并且该程序运行得更快。

我遇到了一些 Microsoft 编译器的麻烦（这里并不意外），这让我浪费了时间； 但是，每个程序员的一个合理方法是在多个编译器中编译他的/她的代码，一些错误和警告不会显示在某些编译器中。

历史 

• 版本 1