计算全排列

问题描述：计算一组数据的全排列

例如：输入1,2,3时，共有3!个排列数，将其从小到大依次排序可分组如下：
------
  123
  132
------
  213
  231
------
  312
  321
解题思路：求长度为n的source[]数组的第x个排列数，其中 0<=n<n!
1)获取排列数的第一个字符
  假设数组长度为n,那么排列数共有n组，每组(n-1)!个，
  所以第 x 个排列数的首字符为 source[x/(n-1)!]
2)获取下一个字符
  在获取了第一个字符之后，问题降级为求长度为n-1的source[]数组的第x%(n-1)!个排列数，
  因此可重复1)的过程，
  当余数x%(n-1)!==0时，数组source[]中所有未使用数据的次序不变，可终止对1)的循环。

 

package org.demo.algorithm;
/**
 * 计算全排列
 */
public class FullSort{
    /**
     * 测试
     */
    public static void main(String[] args){
        FullSort obj = new FullSort();
        // 
        String[] source = {"r","a","e","p"};
        // 计算阶乘
        int size = obj.factorial(source.length);
        for (int i=0; i<size; i++){
        	// 获取第 i 个排列数
            String value = obj.getValue(source,i);
            System.out.println("[" + i + "] " + value);
        }
    }

    /**
     * 从源数据中获取第 x 个排列数
     */
    public String getValue(String[] source,int x){
        int length = source.length;
        // 标记已使用过的数据[0:未使用,1:已使用]
        byte[] used = new byte[length];
        // 用来存储第 x 个排列数
        StringBuilder result = new StringBuilder();
        // 已确定数据个数
        int count = 0;
        for (int i=1; i<length; i++){
            // 取阶乘
            int size = factorial(length - i);
            // 取整
            int m = x/size;
            // 取余
            x = x%size;
            // 从未使用的数据中获取第 m 个数据
            String data = getElementAt(source,m,used);
            // 添加到排列数中
            result.append(data);
            count++;
            // 余数为零时，
            // 剩余的未使用数据在排列数中的顺序同下标顺序
            if (x == 0){
                break;
            }
        }
        // 添加剩余数据
        for (int i=0; i<length && count<length; i++){
            if (used[i] != 1){
                result.append(source[i]);
                count++;
                used[i] = 1;
            }
        }
        return result.toString();
    }
    /**
     * 计算阶乘
     */
    public int factorial(int n){
        if (n == 0 || n == 1){
            return 1;
        }
        int result = 1;
        for (int i=2; i<=n; i++){
            result = result * i;
        }
        return result;
    }
    /**
     * 从未使用的数据中获取第 m 个数据
     */
    public String getElementAt(String[] source,int m,byte[] used){
        int currentIndex = 0;
        for (int i=0; i<source.length; i++){
            if (used[i] != 1){
                if (currentIndex == m){
                    used[i] = 1;
                    return source[i];
                }
                currentIndex++;
            }
        }
        throw new RuntimeException("--程序异常--");
    }
}

  

输出结果：

[0] raep
[1] rape
[2] reap
[3] repa
[4] rpae
[5] rpea
[6] arep
[7] arpe
[8] aerp
[9] aepr
[10] apre
[11] aper
[12] erap
[13] erpa
[14] earp
[15] eapr
[16] epra
[17] epar
[18] prae
[19] prea
[20] pare
[21] paer
[22] pera
[23] pear