全排列算法-递归与字典序的实现方法(Java)

全排列算法-递归与字典序的实现方法(Java)

全排列：

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
例如：

1 、2 、3三个元素的全排列为：

{1，2，3}，{1，3，2}，{2，1，3}，{2，3，1}，{3，1，2}，{3，2，1}。

------------------------------------------------------

解法1（递归）

如下图：要对1、2、3、4进行排序，第一个位置上的元素有四种可能：1或2或3或4，假如已经确定了第一个元素为4，剩下的第二个位置上可以是1、2、3，很显然这具有递归结构，如果原始要排列的数组顺序为1、2、3、4，现在只要分别交换1、2，1、3，1、4然后对剩下的3个元素进行递归的排列。

代码：

-----------------------------------------------

public void Permutation(char chs[],int start )
  {
    if(start==chs.length-1)
    {
      Arrays.toString(chs);
      //如果已经到了数组的最后一个元素，前面的元素已经排好，输出。
    }
    for(int i=start;i<=chs.length-1;i++)
    {
    //把第一个元素分别与后面的元素进行交换，递归的调用其子数组进行排序
        Swap(chs,i,start);
        Permutation(chs,start+1);
        Swap(chs,i,start);
    //子数组排序返回后要将第一个元素交换回来。 
    //如果不交换回来会出错，比如说第一次1、2交换，第一个位置为2，子数组排序返回后如果不将1、2
    //交换回来第二次交换的时候就会将2、3交换，因此必须将1、2交换使1还是在第一个位置 
    }
  }
  public void Swap(char chs[],int i,int j)
  {
    char temp;
    temp=chs[i];
    chs[i]=chs[j];
    chs[j]=temp;
  }

递归方法会对重复元素进行交换比如使用递归对{1，1}进行全排序会输出：{1，1}，{1，1}两个重复的结果。要在排序的时候去掉重复结果，可以修改一下代码如下：

public static void Permutation(char chs[],int start)
  {
    if(start==end)
    {
      list.add(new String(chs));
    }
    for(int i=start;i<=chs.length-1;i++)
    {
      if(i==start||chs[i]!=chs[start])
      {
      //在排列的时候进行判断如果后面的元素与start相同时就不进行排序。
      //这样就可以避免对重复元素进行排序
        Swap(chs,i,start);
        Permutation(chs,start+1);
        Swap(chs,i,start);
      }
    }
  }

解法2（字典序法）

字典序法

对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。

列如：对a、b、c进行排序的结果是{a,b,c}、{a,c,b}、{b,a,c}、{b,c,a}、{c,a,b}、{c,b,a}

字典序法的优点是排列的结果按照顺序输出并且对于重复的元素不进行重复排序。

字典排序法的思想：

例如：对元素1，2，3，4进行排序，假设默认的数组顺序为{1，2，3，4}，先输出第一个排列：1、2、3、4。然后从右向左找到第一个非递增的数，4，3，因为3比4小，交换3、4，并且对3后面的数进行逆序排列，第二个排列为{1，2，4，3}，再从右向左3，4，2，发现2比4小，交换从右向左第一个比2大的数，交换后{1，3，4，2}再对3后面的数进行逆序排列第三个序列为：{1，3，2，4}

依次循环直到数组成为完全递减数组结束1、2、3、4字典排序的最大序列为{4，3，2，1}。

--------------------------------------------

代码

-------------------------------------------

public void PermutationWithDictionary(char chs[])
  {
    Arrays.sort(chs);
    //先对数组的元素进行依次排序
    while(true)
    {
      System.out.println(chs);
      int j=chs.length-1;
      int index=0;
      for(j=chs.length-2;j>=0;j--)
      {
        if(chs[j]<chs[j+1])
        {
          index=j;
          break;
          //从右向左找到第一个非递增的元素
        }
        else if(j==0){
          return;
        }
      }      

      for(j=chs.length-1;j>=0;j--)
      {
        if(chs[j]>chs[index])
          break;
          //从右向左找到第一个比非递增元素大的元素
      }
        Swap(chs,index,j);
        //交换找到的两个元素
        Reverse(chs,index+1);
        //对非递增元素位置后面的数组进行逆序排列
    }    
  }
  public static void Reverse(char chs[],int i)
  {
    int k=i,j=chs.length-1;
    while(k<j)
    {
      Swap(chs,k,j);
      k++;
      j--;
    }
  }

  public static void Swap(char chs[],int i,int j)
  {
    char temp;
    temp=chs[i];
    chs[i]=chs[j];
    chs[j]=temp;
  }

以上这篇全排列算法-递归与字典序的实现方法(Java) 就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持呐喊教程。