排列的生成算法（一）

　　组合数学课程上，介绍到了排列的生成算法。而其中第一个算法——翻转算法，竟是由本课程的任课老师殷奶奶发现的，瞬间感觉到了殷奶奶的强大。殷奶奶在课堂上说，这个算法，是她盯着一个排列数看了两年，同时结合平时她的学生的课程设计想出来的。

　　殷奶奶在课堂上说了算法组成的三要素：

　　算法处理后结果出来的是一张表
　　算法只能由当前一个情况生成下一个情况
　　算法应该是循环的

　　关于这个算法组成的三要素，现在还不是很理解。

　　在这里，由于对这个翻转算法比较敢兴趣，于是将这个算法进行一下简单的介绍，同时用程序实现该算法，通过计算机来实现输出n位数的所有排列。

　　翻转算法：

　　假设一个集合{1，2，…，n}，构造这个集合的所有排列可以按照下面两步进行：

　　（1）将整数n插入集合{1，2，…，n-1}的每一个排列后，得到集合{1，2，…，n}的(n-1)!个不同的全排列；

　　（2）选定（1）中的一个排列，依次将该排列的前i位（i=1，2…，n-1）调到该排列的尾部，得到集合{1，2，…，n}的n个不同排雷。

　　通过以上两步，由乘法原则可知，{1，2，…，n}的(n-1)!*n=n!个不同的排列。

　　对于以上的构造过程，举个例子进行解释：

　　假设已经知道了{1，2，3}的所有的全排列为：

　　{1，2，3}、{2，3，1}、{3，1，2}、{2，1，3}、{1，3，2}、{3，2，1}　　

　　根据{1，2，3}得到{1，2，3，4}的所有排列的过程如下：

　　图片中第一列是如何生成的？

　　首先选择{1，2，3}，然后将4插入到这个排列的末尾，得到{1，2，3，4}，再然后，每次进行一次循环左移，就可以得到2341、3412、4123这几个排列了。对于每一列，进行的步骤都统第一列。就这样，得到了{1，2，3，4}的所有排列情况。

　　一开始，感觉这很简单啊，没什么了不起的地方嘛。但是，真正厉害的地方不在这，而在与如何从4123变化到2314（即第一列的末尾变到第二列的头）？如何从4231变化到3124？这其中的规律是什么？这就是翻转算法的精华的所在。不然，这个就不是一个算法了，因为不满足“循环”这个条件。

　　我们用P4、P3、P2、P1分别表示四个数的位置，P4表示一个排列的第一位，P3表示第二位，其他依次类推。

　　我们从左到右扫描一个排列，当发现第一个Pk(k表示下标)不等于k的时候，即找出第一个该位置上的数不等于他的下标的位置。我们将该位置（包括该位置本身）以前的所有的数翻转后，连接到该排列的末尾，得到一个新的排列。通过这个方法，可以解决上面说的如何从第一列末尾跳到第二列开头的问题。也正是因为这个方法，我们可以生成任意n个数的所有的排列。该算法总结起来如下：

　　（1）从左到右找到第一个这样的位置：他的下标和他的数的值不一样。

　　（2）将包括该数在内的之前的数进行翻转，并接到该排列的末尾，得到一个新的排列

　　（3）直到所有数都满足该位置的数的值与下标的值一致时程序结束。

　　其代码实现如下所示：

/*
Author:xiongmao
Date:2015\11\26 16:26
Title:翻转算法实现n个数的排列的生成 
*/
#include <iostream> 
#include <algorithm>
#include <cstring>
using namespace std;
#define N 100
int c[N];
int myreverse(int arr[],int i,int j)
{
    while(i<=j){
        int temp;
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
        i++;
        j--;
    }
    return 0;
}
int show(int n)
{
    if(n>=100) return -1;
    //按顺序初始化并输出第一个排列，第一个排列为1~n 
    for(int i=1;i<=n;i++){
        c[i]=i;
        cout<<i<<" "; 
    }
    cout<<endl;
    int flag=false;
    while(!flag){
        int index=n;
        for(int i=1;i<=n;i++){
            if(c[i]!=index){
                break;
            }
            index--;
        }
        if(index==0){
            for(int i=1;i<=n;i++){
                cout<<c[i]<<" ";
            }
            cout<<endl;
            flag=true;
            continue;
        }
        myreverse(c,1,n-index+1);
        int temp[N];
        int num=1;
        index=n-index+1;//使得index变为所指向的数的下标 
        for(int i=index+1;i<=n;i++){
            cout<<c[i]<<" ";
            temp[num]=c[i];
            num++;
        }
        for(int i=1;i<=index;i++){
            cout<<c[i]<<" ";
            temp[num]=c[i];
            num++;
        }
        cout<<endl;
        //将当前这个排列重新赋给数组c，用于下次循环 
        memcpy(c,temp,sizeof(c));
    }
}
int main()
{
    int n;
    while(cin>>n&&n!=-1)
    {
        show(n);
    }
}

　　生成的4个数的排列如下图：

排列的生成算法（一）

推荐阅读