两种常用的全排列算法(java)

浏览数：45 / 时间：2015年06月08日

问题：给出一个字符串，输出所有可能的排列。

全排列有多种算法，此处仅介绍常用的两种：字典序法和递归法。

1、字典序法：

如何计算字符串的下一个排列了？来考虑"926520"这个字符串，我们从后向前找第一双相邻的递增数字，"20"、"52"都是非递增的，"26 "即满足要求，称前一个数字2为替换数，替换数的下标称为替换点，再从后面找一个比替换数大的最小数（这个数必然存在），0、2都不行，5可以，将5和2交换得到"956220"，然后再将替换点后的字符串"6220"颠倒即得到"950226"。

算法概括：从后向前遍历，找出第一个交换点，再按照规则找出第二个交换点，将两者进行交换，对第一个交换点之后的字符进行颠倒操作

package algorithm;

import java.util.Arrays;

public class DictionaryPermutation {

    private char[] data;
    private int length;

    public void permutate(String input) {
        // change the data type to we needed
        changeToData(input);
        // sort the data from small to big
        Arrays.sort(data);
        // output all the order
        System.out.println(data);
        while (nextPermutate()) {
            System.out.println(data);
        }
    }

    private void changeToData(String input) {
        if (input == null)
            return;
        data = input.toCharArray();
        length = data.length;
    }

    private boolean nextPermutate() {
        int end = length - 1;
        int swapPoint1 = end, swapPoint2 = end;
        // the actual swap-point is swapPoint1 - 1
        while (swapPoint1 > 0 && data[swapPoint1] <= data[swapPoint1 - 1])
            swapPoint1--;
        if (swapPoint1 == 0)
            return false;
        else {
            while (swapPoint2 > 0 && data[swapPoint2] <= data[swapPoint1 - 1])
                swapPoint2--;
            swap(data, swapPoint1 - 1, swapPoint2);
            reverse(data, swapPoint1, end);
            return true;
        }
    }

    private void swap(char[] data, int left, int right) {
        char temp = data[left];
        data[left] = data[right];
        data[right] = temp;
    }

    private void reverse(char[] data, int left, int right) {
        for (int i = left, j = right; i < j; i++, j--)
            swap(data, i, j);
    }

    public static void main(String... args) {
        DictionaryPermutation p = new DictionaryPermutation();
        p.permutate("aab");
    }

}

2、递归法

为方便起见，用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。

由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122，第一个数与后面交换得212、221。然后122中第二数就不用与第三个数交换了，但对212，它第二个数与第三个数是不相同的，交换之后得到221。与由122中第一个数与第三个数交换所得的221重复了。所以这个方法不行。

换种思维，对122，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。
这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。

（描述从http://blog.csdn.net/hackbuteer1/article/details/6657435处转载）

package algorithm;

public class RecursionPermutation {

    public static void permutate(String input){
        if(input == null)
            throw new IllegalArgumentException();
        char[] data = input.toCharArray();
        permutate(data, 0);
    }
    
    public static void permutate(char[] data, int begin){
        int length = data.length;
        if(begin == length)
            System.out.println(data);
        for(int i = begin ; i < length; i++)
        {
            if(isUnique(data, begin, i)){
                swap(data, begin, i);
                permutate(data, begin + 1);
                swap(data, begin, i);
            }                
        }
    }
    
    private static boolean isUnique(char[] data, int begin, int end){
        for(int i = begin; i < end; i++)
            if(data[i] == data[end])
                return false;
        return true;
    }
    
    private static void swap(char[] data, int left, int right) {
        char temp = data[left];
        data[left] = data[right];
        data[right] = temp;
    }
    
    
    public static void main(String... args){
        RecursionPermutation.permutate("aac");
    }

}