非递归，按序输出集合的全排列

题目描述
非递归，按序输出集合全排列，是在笔试面试中经常考的问题。递归输出集合的全排列相对来说还是比较简单的，而非递归实现这个问题需要一些小技巧。
全排列是将集合中的元素（可以为数字，可以为字符），按照字典序生成所有排列的集合，并输出这些排列。以数字集合距离，集合{1,2,3}的按序全排列为：

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

这样3个元素一共生成了6个排列，即M个元素会生成M！个全排列序列。

非递归思路
递归的解题方法有时间另开一文叙述，这里要介绍的是非递归的思路。还是同样的以数字集合{1,2,3}为例。

这个集合生成的有序序列集合中的第一个序列是1 2 3，这个很容易能够看出。问题是如何根据该序列生成下一个有序的序列呢？下一个有序序列在字典序上刚刚好大于前一个序列，应该是1 3 2，可用看出是将第一个序列中的2和3交换位置得到。而1 3 2之后的下一个序列是2 1 3，是将最后一个2放到了1的前面。在2 1 3之后是2 3 1，是在2 1 3的基础上将最后的3换到了1的前面。一个很直观的感觉就是从后向前查找，遇到合适的数的时候与前面某一个数字交换。

具体算法描述，以数字集合{1,2,3}为例：

1，第一个序列就是当前集合元素连起来本身。

2，从后向前查找后面的数大于前面的数对（从小到大，称其为逆序对），找不到说明所有的排列均已经生成（即从123到了321），若找到（例如2 1 3中的 1和3就是一个逆序对）则停下来。

3，以213为例，就是记住3的位置为i，再从后向前查找数，要找到刚刚好大于1（位置为i-1）的数，这里很显然还是3。

4，交换第三步找到的数与位置为i-1的数。

5，逆置从位置i开始到集合结尾的所有的数，例如从*****321（位置i为3）到*****123（位置i为1）。

6，重复这一过程，直到找不到逆序对，则生成了所有的序列。

简单示例代码

[cpp]
void swap(int *p,int*q)
{
    int tmp;
    tmp=*p;
    *p=*q;
    *q=tmp;
}

void mknewseq(int *data,int start, int last)
{
    while(start<last)
    {
        swap(&data[start],&data[last]);
        start++;
        last--;

    }
}

void showdata(int *data,int num)
{
    int i=0;
    for(i=0;i<num;i++)
    {
        printf(" %d ",data[i]);
    }
    printf("\n");
}
int findall(int *data,int num)
{
    int i,j;
    int lastdata=num-1;
    int tmp;

    for(i=lastdata;i>0;i--)
    {
        if(data[i]>data[i-1]) break;
    }
    if(0==i) return 0;
    tmp=i;
    for(j=lastdata;j>=i;j--)
    {
        if((data[j]>data[i-1])&&(data[j]<data[tmp]))
            tmp=j;
    }

    swap(&data[tmp],&data[i-1]);

    mknewseq(data,i,lastdata);

    return 1;

}

int main()
{
    int data[4]={1,2,3,4};
    showdata(data,4);
    while(findall(data,4)){

        showdata(data,4);
    }
    return 0;
}

补充：软件开发 , C++ ,