全排列生成算法 .-阿里云开发者社区

原文讲的很详细了，为了完整性，这里粘贴的参考链接中大部分文字，并且在原文的基础上，添加了“给定某个排列，求其字典序中上一个元素”的算法。

字典序

全排列生成算法的一个重要思路，就是将集合A中的元素的排列，与某种顺序建立一一映射的关系，按照这种顺序，将集合的所有排列全部输出。这种顺序需要保证，既可以输出全部的排列，又不能重复输出某种排列，或者循环输出一部分排列。字典序就是用此种思想输出全排列的一种方式。这里以A{1,2,3,4}来说明用字典序输出全排列的方法。

首先，对于集合A的某种排列所形成的序列，字典序是比较序列大小的一种方式。以A{1,2,3,4}为例，其所形成的排列1234<1243，比较的方法是从前到后依次比较两个序列的对应元素，如果当前位置对应元素相同，则继续比较下一个位置，直到第一个元素不同的位置为止，元素值大的元素在字典序中就大于元素值小的元素。上面的a1[1...4]=1234和a2[1...4]=1243，对于i=1,i=2，两序列的对应元素相等，但是当i=2时，有a1[2]=3<a2[2]=4，所以1234<1243。

求字典序的下一个全排列：

使用字典序输出全排列的思路是，首先输出字典序最小的排列，然后输出字典序次小的排列，……，最后输出字典序最大的排列。这里就涉及到一个问题，对于一个已知排列，如何求出其字典序中的下一个排列。这里给出算法。

对于排列a[1...n]，找到所有满足a[k]<a[k+1](0<k<n-1)的k的最大值，如果这样的k不存在，则说明当前排列已经是a的所有排列中字典序最大者，所有排列输出完毕。
在a[k+1...n]中，寻找满足这样条件的元素l，使得在所有a[l]>a[k]的元素中，a[l]取得最小值。也就是说a[l]>a[k]，但是小于所有其他大于a[k]的元素。
交换a[l]与a[k].
对于a[k+1...n]，反转该区间内元素的顺序。也就是说a[k+1]与a[n]交换，a[k+2]与a[n-1]交换，……，这样就得到了a[1...n]在字典序中的下一个排列。

这里我们以排列a[1...8]=13876542为例，来解释一下上述算法。首先我们发现，1(38)76542，括号位置是第一处满足a[k]<a[k+1]的位置，此时k=2。所以我们在a[3...8]的区间内寻找比a[2]=3大的最小元素，找到a[7]=4满足条件，交换a[2]和a[7]得到新排列14876532，对于此排列的3～8区间，反转该区间的元素，将a[3]-a[8]，a[4]-a[7]，a[5]-a[6]分别交换，就得到了13876542字典序的下一个元素14235678。

求字典序的上一个全排列：

从前面的的分析，我们可以进行逆推导，求得上一个排列，这里的算法如下：

1. 对于排列a[1..n],从尾端开始，找到第一个a[k]>a[k+1]并记录，若k<0，则说明a已经是字典序的最小者。

2. 在a[k+1..n]中，寻找小于a[k]的最大元素a[i]，

3. 交换a[k]和a[i]的值，

4. 对于a[k+1..n]，反转区间内元素的顺序。

这里我们还是以前面的例子来说明，初始时，a=14235678，首先找到1(42)35678，此时k=2，再找到比4小的最大数是3，此时a[i]=3, i=4, 交换a[i]和a[k]的值，得到a=13245678，最后反转a[k+1..n]，得到最后的结果a=13876542。

C代码如下：

[cpp] view plain copy print ?

/*
http://t.jobdu.com/thread-98707-1-1.html
1、写出一个算法来生成1-n的全排列
2、已知一个长度为N的序列A，它的每个元素是1-N之间的任何一个元素，且两两不重复，称他为一个排列，写出一个算法生成该排列的字典序的下一排列。例如，A=[3 2 1 4]，则下一排列为A'=[3 2 4 1]，A'的下一排列为A''=[3 4 1 2]，以此类推。
http://blog.csdn.net/joylnwang/article/details/7064115
*/
#include <stdio.h>
void swap(char* array, unsigned int i, unsigned int j)
{
char t = array[i];
array[i] = array[j];
array[j] = t;
}
// 递归输出序列的全排列
void fullPermutation(char* arr, int len, int index)
{
int i;
if (index >= len)
printf("%s\n", arr);
else
{
for (i = index; i < len; i++)
{
swap(arr, index, i);
fullPermutation(arr, len, index+1);
swap(arr, index, i);
}
}
}
void reverse(char arr[], int start, int end)
{
if (start >= end)
return;
int len = start - end + 1;
int i;
for (i = 0; i <= len/2; i++)
{
swap(arr, start+i, end-i);
}
}
int pre_permutation(char arr[], int len)
{
int k, i, max, max_i;
for (i = len-2; i >= 0; i--)
{
if (arr[i] > arr[i+1])
{
k = i;
break;
}
}
if (i < 0)
{
printf("%s is the first permutation\n", arr);
return -1;
}
max_i = k + 1;
max = arr[max_i];
for (i = k+1; i < len; i++)
{
if (arr[i] < arr[k] && arr[i] > max)
{
max_i = i;
max = arr[max_i];
}
}
if (max_i < len)
{
swap(arr, k, max_i);
reverse(arr, k+1, len-1);
}
return 0;
}
int next_permutation(char arr[], int len)
{
int k, i, min, min_i;
for (k = len-2; k >= 0; k--)
{
if (arr[k] < arr[k+1])
break;
}
if (k < 0)
{
printf("%s is the last permutation\n", arr);
return -1;
}
min = arr[k+1];
min_i = k+1;
for (i = k + 1; i < len; i++)
{
if (arr[i] > arr[k] && arr[i] < min)
{
min_i = i;
min = arr[i];
}
}
if (min_i < len)
{
swap(arr, k, min_i);
reverse(arr, k+1, len-1);
}
return 0;
}
int main()
{
int i = 1;
char arr[] = "1234";
int len = sizeof(arr) / sizeof(arr[0]) - 1;
//fullPermutation(arr, len, 0); // 递归打印全排列
// 按照字典序输出全排列
printf("next_permutation demo:\n");
do
{
printf("%02d: %s\n", i, arr);
i++;
} while (next_permutation(arr, len) >= 0);
i = 1;
printf("\npre_permutation demo:\n");
do
{
printf("%02d: %s\n", i, arr);
i++;
}
while (pre_permutation(arr, len) >= 0);
return 0;
}

/*
http://t.jobdu.com/thread-98707-1-1.html
1、写出一个算法来生成1-n的全排列
2、已知一个长度为N的序列A，它的每个元素是1-N之间的任何一个元素，且两两不重复，称他为一个排列，写出一个算法生成该排列的字典序的下一排列。例如，A=[3 2 1 4]，则下一排列为A'=[3 2 4 1]，A'的下一排列为A''=[3 4 1 2]，以此类推。
http://blog.csdn.net/joylnwang/article/details/7064115
*/

#include <stdio.h>

void swap(char* array, unsigned int i, unsigned int j)
{
    char t = array[i];
    array[i] = array[j];
    array[j] = t;
}

// 递归输出序列的全排列
void fullPermutation(char* arr, int len, int index)
{
    int i;
    if (index >= len)
        printf("%s\n", arr);
    else
    {
        for (i = index; i < len; i++)
        {
            swap(arr, index, i);
            fullPermutation(arr, len, index+1);
            swap(arr, index, i);
        }
    }
}

void reverse(char arr[], int start, int end)
{
    if (start >= end)
        return;
    int len = start - end + 1;
    int i;
    for (i = 0; i <= len/2; i++)
    {
        swap(arr, start+i, end-i);
    }
}

int pre_permutation(char arr[], int len)
{
    int k, i, max, max_i;
    for (i = len-2; i >= 0; i--)
    {
        if (arr[i] > arr[i+1])
        {
            k = i;
            break;
        }
    }
    if (i < 0)
    {
        printf("%s is the first permutation\n", arr);
        return -1;
    }
    max_i = k + 1;
    max = arr[max_i];
    for (i = k+1; i < len; i++)
    {
        if (arr[i] < arr[k] && arr[i] > max)
        {
            max_i = i;
            max = arr[max_i];
        }
    }
    if (max_i < len)
    {
        swap(arr, k, max_i);
        reverse(arr, k+1, len-1);
    }
    return 0;
}

int next_permutation(char arr[], int len)
{
    int k, i, min, min_i;
    for (k = len-2; k >= 0; k--)
    {
        if (arr[k] < arr[k+1])
            break;
    }
    if (k < 0)
    {
        printf("%s is the last permutation\n", arr);
        return -1;
    }
    min = arr[k+1];
    min_i = k+1;
    for (i = k + 1; i < len; i++)
    {
        if (arr[i] > arr[k] && arr[i] < min)
        {
            min_i = i;
            min = arr[i];
        }
    }
    if (min_i < len)
    {
        swap(arr, k, min_i);
        reverse(arr, k+1, len-1);
    }
    return 0;
}

int main()
{
    int i = 1;
    char arr[] = "1234";
    int len = sizeof(arr) / sizeof(arr[0]) - 1;
    //fullPermutation(arr, len, 0); // 递归打印全排列

    // 按照字典序输出全排列
    printf("next_permutation demo:\n");
    do
    {
        printf("%02d: %s\n", i, arr);
        i++;
    } while (next_permutation(arr, len) >= 0);

    i = 1;
    printf("\npre_permutation demo:\n");
    do
    {
        printf("%02d: %s\n", i, arr);
        i++;
    }
    while (pre_permutation(arr, len) >= 0);

    return 0;
}

全排列生成算法 .

热门文章

最新文章

相关课程

相关电子书

相关实验场景