全排列算法分析(原创方法/一般方法/字典序法)

问题重述:

全排列算法即对给定的一个序列,输出其所有不同的(n!种)排列,例如:

给定序列{1, 2, 3}有{1, 2, 3}、{1, 3, 2}、{2, 1, 3}、{2, 3, 1}、{3, 1, 2}、{3, 2, 1}这6种排列

好像很容易就能写出来,对于更长的序列也只是时间问题,最终肯定能够用笔一一列出来。但是要用程序实现的话,可能让人有点无从下手(乍看好像很简单),下面给出三种不同的解全排列的方法:

一.原创方法

所谓的原创方法就是不考虑算法的效率及其他因素,完全为了解决问题而自己去构造一种可行的方法(不一定好,但能解决问题)

首先,让我们想想自己是如何写出上面的6个序列的

  1. 确定第一位上的元素,有三种可能:1, 2, 3
  2. 确定第二位上的元素(以1为例),有两种可能:2, 3
  3. 确定第三位上的元素(以2为例),只有一种可能:3。这时我们就得到了一个序列:1, 2, 3

接下来,让我们理一理思路,想想用程序如何实现。对于一个长度为n的序列来说,计算机要做的就是:

  • 1.确定第(i)位上的元素,有(n + 1 – i)种可能,依次选择一种可能作为第i位的元素,保存当前已经确定的序列(长度为i)
  • 2.确定第(i+1)位上的元素,有(n + 1 – i – i)种可能,依次选择一种可能作为第i + 1位的元素,保存当前已经确定的序列(长度为i + 1)
  • 。。。
  • n.确定第(n)位上的元素,只有一种可能,将唯一的可能元素作为第n位上的元素,输出已经确定的序列

显然,这是一种递归的方法。Java代码如下:

public class FullPermutation {
    static int count = 0;
    //递归实现全排列
    //程序思路是:依次确定第一位到最后一位,与人的一般思维方式一致
    public static void main(String[] args) {
        String str = "13234";
        str = check(str);//去除重复元素
        fullPermutate(0, "", str);
        System.out.print(count);
    }
    //@param index 本次调用确定第index位
    //@param path 已经确定顺序的串
    //@param string 待全排列的串
    static void fullPermutate(int index, String path, String string)
    {
        String restStr = strSub(string, path);
        if(index == string.length())
        {
            System.out.println(path + restStr);
            count++;//
            return;
        }
        else
        {
            for(int i = 0;i < string.length() - index;i++)
                fullPermutate(index + 1, path + restStr.charAt(i), string);
        }
    }
    //@param full 完整的串
    //@param part 部分子串
    //@return rest 返回full与part的差集
    static String strSub(String full, String part)
    {
        String rest = "";
        for(int i = 0;i < full.length();i++)
        {
            String c = full.charAt(i) + "";
            if(!part.contains(c))
                rest += c;
        }
        return rest;
    }
    //@param str 待检查的串
    //@return 返回不含重复元素的串
    static String check(String str)
    {
        for(int i = 0;i < str.length() - 1;i++)
        {
            String firstPart = str.substring(0, i + 1);
            String restPart = str.substring(i + 1);
            str = firstPart + restPart.replace(str.charAt(i) + "", "");
        }
        return str;
    }
}

P.S.至于上面的代码中为什么要去除参数中的重复元素,是为了增强程序的鲁棒性,经典的排列问题是针对不含重复元素的序列而言的,含重复元素的序列我们将在后面展开讨论

二.一般算法(最常见的,也是最经典的全排列算法)

核心思想是交换,具体来说,对于一个长度为n的串,要得到其所有排列,我们可以这样做:

  1. 把当前位上的元素依次与其后的所有元素进行交换
  2. 对下一位做相同处理,直到当前位是最后一位为止,输出序列

(需要注意的一点:我们的思想是“交换”,也就是直接对原数据进行修改,那么在交换之后一定还要再换回来,否则我们的原数据就发生变化了,肯定会出错)

如果觉得上面的解释还是很难懂的话,那么记住这句话:核心思想就是让你后面的所有人都和你交换一遍(而你是一个指针,从前向后按位移动…)。C代码如下:(摘自http://www.cnblogs.com/nokiaguy/archive/2008/05/11/1191914.html

#include <stdio.h>
int n = 0;
void swap(int *a, int *b) {
int m; m = *a; *a = *b; *b = m; }
void perm(int list[], int k, int m) { int i;
if(k > m)
{
for(i = 0; i <= m; i++)
printf("%d ", list[i]);
printf("\n");
n++;
}
else
{
for(i = k; i <= m; i++)
{
swap(&list[k], &list[i]);
perm(list, k + 1, m);
swap(&list[k], &list[i]);
}
} } int main() {
int list[] = {1, 2, 3, 4, 5};
perm(list, 0, 4);
printf("total:%d\n", n);
return 0; }

原文也给出了一点解释,但如果还是不能理解的话,不妨输出一下运行轨迹,有助于理解,或者用笔画一画,多看几遍就明白了,直接看代码的话确实不好理解

三.字典序法

其实在本文开头给出的例子中就用了字典序,人写全排列或者其它类似的东西的时候会不自觉的用到字典序,这样做是为了防止漏掉序列

既然如此,用字典序当然也能实现全排列,对于给定序列{3, 1, 2},我们理一理思路,想想具体步骤:

  1. 对给定序列做升序排序,得到最小字典序{1, 2, 3}
  2. 对有序序列求下一个字典序,得到{1, 3, 2}
  3. 如果当前序列没有下一个字典序(或者说当前序列是最大字典序,如{3, 2, 1}),则结束

显然字典序法的核心是:求下一个字典序,要充分理解这里的“下一个”,有两层意思:

  1. 该序列在字典中是排在当前序列后面的
  2. 该序列是字典中最靠近当前序列的

字典序有严格的数学定义,按照定义就能求出一个序列的下一个字典序,具体做法不在此展开叙述(下面的代码中有细致的解释)。Java代码如下:

public class DictionaryOrder {
    //按字典序输出全排列
    //按照字典序可以得到已知序列的下一个序列,可以用于不需要得到所有全排列的场合(例如数据加密)
    public static void main(String[] args) {
        int arr[] = new int[]{4, 3, 1, 2};
//      boolean exist = nextPermutation(arr);
//      if(exist)
//      {
//          for(int value : arr)
//              System.out.print(value);
//          System.out.println();
//      }
//      else
//          System.out.println("当前序列已经是最大字典序列");
        //对给定序列排序(升序)
        sort(arr);
        for(int value : arr)
            System.out.print(value);
        System.out.println();
        //求全排列并输出
        int count = 1;//第一个已经在上面输出了
        while(nextPermutation(arr))
        {
            for(int value : arr)
                System.out.print(value);
            System.out.println();
            count++;
        }
        System.out.println("共 " + count + " 个");
    }
    //@param arr 当前序列
    //@return 字典序中的下一个序列,没找到则返回false
    public static boolean nextPermutation(int[] arr)
    {
        int pos1 = 0, pos2 = 0;
        //1.从右向左找出满足arr[i] < arr[i + 1]的i
        //(就是找出相邻位中满足前者小于后者关系的前者的位置)
        boolean find = false;
        for(int i = arr.length - 2;i >= 0;i--)
            if(arr[i] < arr[i + 1])
            {
                pos1 = i;
                find = true;
                break;
            }
        if(!find)//若没找到,说明当前序列已经是最大字典序了
            return false;
        //2.从pos1向后找出最小的满足arr[i] >= arr[pos1]的i
        //(就是找出pos1后面不小于arr[pos1]的最小值的位置)
        int min = arr[pos1];
        for(int i = pos1 + 1;i < arr.length;i++)
        {
            if(arr[i] >= arr[pos1])
            {
                min = arr[i];
                pos2 = i;
            }
        }
        //3.交换pos1与pos2位置上的值
        int temp = arr[pos1];
        arr[pos1] = arr[pos2];
        arr[pos2] = temp;
        //4.对pos1后面的所有值做逆序处理(转置)
        int i = pos1 + 1;
        int j = arr.length - 1;
        for(;i < j;i++, j--)
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        return true;
    }
    //对给定数组做升序排序(冒泡法)
    //@param arr 待排序数组
    public static void sort(int[] arr)
    {
        for(int i = 0;i < arr.length - 2;i++)
            for(int j = 0;j < arr.length - i - 1;j++)
                if(arr[j] > arr[j + 1])
                {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
    }
}

算法细节就到这里,下面讨论几个无关紧要问题:

1.给定序列中存在重复元素

经典的全排列问题不讨论这个问题,但实际应用中可能会遇到,我们有两个选择:

a.对原数据(给定序列)进行处理,对于重复元素只保留一个,或者对重复元素做替换,例如对{1, 1, 2, 3, 2},我们建立一张替换表,a = 1, b = 2,原数据处理结果为{1, a, 2, 3, b},至此我们就消除了重复元素

b.对算法做修改,检测重复元素并做相应处理,需要结合具体数据特征做处理

2.算法效率问题

如果复杂问题中需要用到全排列,那么不得不考虑算法效率问题了,上面给出的算法中,前两种时间复杂度相同,都是n层递归,每层n-i + 1个循环

第三种算法的时间复杂度主要集中在了排序上,如果给定序列已经有序,那么此时第三种算法无疑是最佳的

另外,还有一种新颖的全排列算法,有兴趣的话也可以试一试,原文链接:http://supershll.blog.163.com/blog/static/37070436201171005758332/

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code