全排列算法:递归和非递归实现

参考资料：http://blog.csdn.net/e3399/article/details/7543861

如果要求C(n,m)，例如C(5,2)=5!/(2!*3!)=10，就参考http://www.cnblogs.com/qrlozte/p/3497035.html

如果要求P(n,n)，例如P(3,3)=3!=6，就使用本文章提到的全排列算法

如果要求P(n,m)，例如P(5,2)=5!/(5-2)!=20，就先求C(n,m)，然后对每一个组合求P(m,m)即可，因为P(n,m)=C(n,m)*P(m,m)

1.非递归实现 next_permutation

　　1.1 基本思想

　　　　注：此算法要求被排列的各个元素之间具有“Natural Order”，也就是说这些元素可以组成一个有序的序列，在JAVA中可以通过实现Comparable来完成

　　　 1.对初始队列进行排序，找到所有排列中最小的一个排列Pmin。
　　　 2.找到刚刚好比Pmin大比其它都小的排列P(min+1)。
　　　 3.循环执行第二步,直到找到一个最大的排列,算法结束。

　　　　　例如排列ABCDE，这是所有排列中最小的一个排列，刚好比ABCDE大的排列是：ABCED。

　　1.2 算法描述

　　　　给定已知序列P = A1A2A3.....An
　　　　对P按字典排序，得到P的一个最小排列Pmin = A1A2A3....An ，满足Ai > A(i-1) (1 < i <= n)
　　　　从Pmin开始,找到刚好比Pmin大的一个排列P(min+1)，再找到刚好比P(min+1)大的一个排列，如此重复。
　　　　1.从后向前（即从An->A1）,找到第一对为升序的相邻元素，即Ai < A(i+1)。
　　　　　　若找不到这样的Ai，说明已经找到最后一个全排列，可以返回了。
　　　　2.从后向前,找到第一个比Ai大的数Aj，交换Ai和Aj。
　　　　3.将排列中A(i+1)A(i+2)....An这个序列的数逆序倒置，即An.....A(i+2)A(i+1)。因为由前面第1、2可以得知，A(i+1)>=A(i+2)>=.....>=An,这为一个升序序列，应将该序列逆序倒置，所得到的新排列才刚刚好比上个排列大。
　　　　4.重复步骤1-3,直到返回。

　　1.3 代码

/* Print the all-permutation of the given int array. */
void next_permutation(int a[], int length)
{
    if (length < 2)
    {
        return;
    }
    
    while (true)
    {
        print_array(a, length); // print the permutation

        int i, j;
        for (i = length-2; i >= 0; --i)
        {
            if (a[i] < a[i + 1])
                break;
            else if (i == 0)
                return;
            else
                ;
        }
        for (j = length-1; j > i; --j)
        {
            if (a[j] > a[i])
                break;
            else
                ;
        }
        swap(a, i, j);
        reverse(a, i + 1, length - 1);
    }
}

/* Reverse the elements between a[i] and a[j], inclusive. */
void reverse(int a[], int i, int j)
{
    for (; i<j; i++, j--)
    {
        swap(a, i, j);
    }
}

/* Swap two elements in an int array. */
void swap(int *a, int i, int j)
{
    a[j] ^= a[i];
    a[i] ^= a[j];
    a[j] ^= a[i];
}

/* Print an int array to the standard output stream. */
void print_array(int a[], int length)
{
    std::cout << "[";
    for (int i = 0; i < length-1; i++)
    {
        std::cout << a[i] << ", ";
    }
    std::cout << a[length-1] << "]" << std::endl;
}

2.递归实现

　　参考http://blog.csdn.net/e3399/article/details/7543861

全排列算法:递归和非递归实现

推荐阅读