字典序法求全排列

就当一个笔记嘻嘻

来来来先看一下算法的过程
给定一个字符串str，我们可以按照如下步骤找到比该字符串str大一位的下一个排列合租
1、从右向左找开始下降的位置，即第一次出现i-1 < i的位置索引 i
1.1、找到头也没有这样的情况时候，结束，说明该组合是最大的情况了
2、从i-1 的位置开始向右找 最后一个比str[i-1]大的数max，该数max的索引位置 j
3、交换 str[i-1] 和 str[j] 的值
4、把i-1之后的位置（不包括i-1）的值进行翻转，即得到下一个较大的排列组合

来想一下为什么这么做可行呢

我们是要找下一个大的对不对，所以找到前面小的数lit 和 后面 比该数lit 大， 并且是大中的 最小的那个数lar，然后交换他们，就相当于把后面最大的，但又是最小的那个数放到前面，把前面的小数放到后面去，大的数放到前面来，按照字典序，自然变大了，接下来再进行一个翻转，又把后面的较大的数放到了后面去，小的又靠前了。

如：
str=2143
1、2 > 1 < 4 > 3，1 < 4,所以在i = 2的时候开始下降,i-1 = 1
1.1、还没有结束
2、最后一个 比str[i-1]=1 大 的数 是 str[3] = 3
3、交换1（str[i-1]） 和 3 (str[3]) ---> 2341
4、倒置str[i-1]后面的位置--->2314

看一个重复的情况：str=aab
aab i=2 i-1=1
str[i-1] =a < str[2] = b
交换i-1和2：aba
倒置i-1=1之后的：aba (i-1后面就一位)

aba i=1, i-1 = 0
str[i-1] = a < str[1] = b
交换i-1和1：baa
倒置i-1=0之后的：baa

aab aba baa

该算法的好处：1、能够到达去重效果，2、能够预知下一个排列组合，3、时间复杂度相对低，并且能够达到1和2的效果

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;

public class Solution {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        Solution test = new Solution();
        ArrayList<String> abc = test.Permutation("123456789");
        System.out.println(System.currentTimeMillis() - start);
        System.out.println(JSON.toJSONString(abc));
    }

    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<String>();
        if(str == null || str.length() == 0) return result;
        result.add(str);
        char[] chars = str.toCharArray();
        while (true) {
            int i = findPreMin(chars);
            if(i == -1) {
                break;
            }
            int j = findForMax(chars, i);
            swap(chars, i - 1, j);
            inverse(chars, i);
            result.add(String.valueOf(chars));
        }
        return result;
    }

    /**
     * 翻转指定位置后面部分
     * @param str
     * @param index
     * @return
     */
    public void inverse(char[] str, int index) {
        int i=index, j=str.length - 1;
        while (true) {
            // 奇数个
            if(i == j) {
                break;
            }
            // 偶数个
            if(j - i == 1) {
                swap(str, i, j);
                break;
            }
            swap(str, i, j);
            i++;
            j--;
        }
    }

    /**
     * 交换 指定两个位置 的值
     * @param str
     * @param index1
     * @param index2
     * @return
     */
    public void swap(char[] str, int index1, int index2) {
        char tmp1 = str[index1];
        str[index1] = str[index2];
        str[index2] = tmp1;
    }

    /**
     * 向左找到下降点的坐标
     * @param str
     * @return
     */
    public int findPreMin(char[] str) {
        int length = str.length;
        for(int i=length-1; i>0; i--) {
            if(str[i-1] < str[i]) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 向右找到 比 指定位置index 大的 最小的 那个数的坐标
     * @param str
     * @param index
     * @return
     */
    public int findForMax(char[] str, int index) {
        /*for(int i=index; i<str.length; i++) {
            if(str[index] < str[i] && str[index] > str[i+1]) {
                return i;
            }
        }
        return str.length-1;*/
        int minMaxIndex = index;
        while(minMaxIndex < str.length && str[minMaxIndex] > str[index-1]) {
            minMaxIndex ++;
        }
        return minMaxIndex - 1;
    }
}