产生下一个排列数的算法

全排序：
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。例如n=3，全排序为：123、132、213、231、312、321共6种。

字典序法：
对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是：从左到右逐个比较对应的字符大小。字符集{1,2,3}，较小的数字较先，这样按字典序生成的全排列即：123、132、213、231、312、321。

1.现在假设输入全排序中的一串数字，要求得到它在字典序全排列中对应的下一个排列数。比如：输入123输出132，输入12435输出12453。

算法思想：

1.从数列的右边向左寻找连续递增序列, 例如对于：1,3,5,4,2，其中5-3-2即为递增序列。

2.从上述序列中找一个比它前面的数（3）大的最小数（4），并将且交换这两个数。于是1,3,5,4,2->1,4,5,3,2，此时交换后的依然是递增序列。

3.新的递增序列逆序，即：1,4,5,3,2 => 1,4,2,3,5

#include <iostream>
using namespace std;

void swap(int * a, int * b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

//产生下一个排列数
//存在则返回1
//不存在返回0
int next(int a[], int n)
{
    int i,j,k;
    // 从右向左寻找非递减序列,例如对于序列1,3,5,4,2,将会找到数字5的位置
    for(k = n - 1; k > 0 && a[k - 1] >= a[k]; k--);
    if(k == 0) return 0; //例:对于5,4,3,2,1的情形，他的下一个不存在，返回0
    //从非递减序列李寻找比它前面的一个数(3)大的最小数,即数字4
    for(i = n - 1; a[i] <= a[k - 1]; i--);
    //交换3和4
    swap(&a[k - 1], &a[i]);
    //将新的非递减序列逆序
    i = k;
    j = n - 1;
    while(i < j) swap(&a[i++], &a[j--]);
    return 1;
}

void pnt(int a[], int n)
{
    int i;
    for(i = 0; i < n; ++i) printf("%d ", a[i]);
    printf("
");
}

int main()
{
    int a[] = {1,2,3,4};
    int size = sizeof(a) / sizeof(a[0]);
    pnt(a, size);
    while(next(a, size))
        pnt(a, size);
    return 0;
}

2.全排序的递归实现

全排序是将一组数按一定顺序排列，如果这组数有n个，那么全排列有n!个。

如果只有两个数2和3，那么全排序是23和32；如果再添加一个数1，那么全排序为123,132,213,231,312,321。所以全排序就是将数组中的所有数分别和第一个数交换，然后再添加剩下n-1个数的全排列即可，典型的递归思想。

算法思想：

1.将字符串中第一个字符与后面的第k个字符交换（初始值k=2）

2.计算除去第一个字符的串的全排序

3.将第一个字符和第k个字符交换（恢复原来的字符串），然后k+=1，回到第一步，直至k=length.

#include <iostream>  
using namespace std;

void Swap(char *a, char *b)  
{  
    char temp = *a;  
    *a = *b;  
    *b = temp;  
}  
//k表示当前选取到第几个数,m表示共有多少数.  
void AllRange(char *pszStr, int k, int m)  
{  
    if (k == m)  
    {   
        printf("%s
", pszStr);  
    }  
    else  
    {  
        for (int i = k; i <= m; i++)
        {  
            Swap(pszStr + k, pszStr + i);  
            AllRange(pszStr, k + 1, m);  
            Swap(pszStr + k, pszStr + i);  
        }  
    }  
}  

int main()  
{  
    char szTextStr[] = "123";  
    AllRange(szTextStr, 0, strlen(szTextStr) - 1); 
    return 0;  
}

上面的程序没有考虑到重复数字，如122将会输出：122,122,212,221,221,212。而实际应输出的是122,212,221，对于相同的数，只需要和这些相同数中的第一个交换就可以了，比如12324，在2324中只需要和第一个2交换即可得到2开头的全部全排列了。用编程的话描述就是第i个数与第j个数交换时，要求[i,j)中没有与第j个数相等的数。

//在pszStr数组中，[nBegin,nEnd)中是否有数字与下标为nEnd的数字相等  
bool IsSwap(char *pszStr, int nBegin, int nEnd)  
{  
    for (int i = nBegin; i < nEnd; i++)  
        if (pszStr[i] == pszStr[nEnd])  
            return false;  
    return true;  
}  
//k表示当前选取到第几个数,m表示共有多少数.  
void AllRange(char *pszStr, int k, int m)  
{  
    if (k == m)  
    {  
        printf("%s
", pszStr);  
    }  
    else  
    {  
        for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列  
        {  
            if (IsSwap(pszStr, k, i))  
            {  
                Swap(pszStr + k, pszStr + i);  
                AllRange(pszStr, k + 1, m);  
                Swap(pszStr + k, pszStr + i);  
            }  
        }  
    }  
}

3.全排序的非递归实现

全排序的非递归实现，就是先要考虑如何计算字符串的下一个排列（问题1）。只要对字符串反复求下一个排序，最终即可得到全排序。这里注意：输入的串需要预先由小到大排序（构建全排序的第一个串）。

int QsortCmp(const void *pa, const void *pb)  
{  
    return *(int*)pa - *(int*)pb;  
}  

int main()
{
    int a[] = {3,1,2};
    int size = sizeof(a) / sizeof(a[0]);
    qsort(a, size, sizeof(a[0]), QsortCmp);
    pnt(a, size);
    while(next(a, size))
        pnt(a, size);
    return 0;
}

PS：

把一个问题映射到二进制数，有很多好玩儿的题目：
有1000瓶老鼠药和10只老鼠，其中有一瓶老鼠药是有毒的，老鼠喝了有毒的老鼠药2天就会挂掉，如何在两天之内找到哪瓶老鼠药是有毒的？(tips：老鼠列成一排，每只老鼠看成一个bit位，1~1000给对应bit位是1的老鼠喝，最后挂掉的老鼠是药瓶编号的 bit位1(其它是0)，该瓶老鼠药是有毒的)