有条件的全排列

题目：对 {1, 2, 2, 3, 4, 5} 进行无重复的全排列，要求 4 不在第三位，且 3，5 不相连。
思路：用 roll() 方法递归构造所有全排列，将每个构造出的排列做判断之后存入结果集。

java 代码

import java.util.ArrayList;

/**
 * 对 {1, 2, 2, 3, 4, 5} 进行无重复的全排列，要求 4 不在第三位，且 3，5 不相连。
 *
 * @author <a href="mailto:[e-mail]">yidinghe</a>
 */
public class AllSort {

    static ArrayList<int[]> results = new ArrayList<int[]>();

    public static void main(String[] args) {
        int[] ints = {1, 2, 2, 3, 4, 5};
        roll(ints, 0);
        for (int[] result : results) {
            printArr(result);
        }
        System.out.println("结果数量：" + results.size());
    }

    /**
     * 递归构造全排列假设要排列的数组已经从小到大排好序。
     *
     * @param ints    要排列的数组
     * @param pointer 进行排列的起始位置
     */
    private static void roll(int[] ints, int pointer) {
        if (ints.length < 2) {
            return;
        }

        if (pointer == ints.length - 1) {
            saveResult(ints);
            return;
        }

        int[] cloned;
        for (int i = pointer; i < ints.length; i++) {
            cloned = ints.clone();
            int t = cloned[i];
            cloned[i] = cloned[pointer];
            cloned[pointer] = t;

            roll(cloned, pointer + 1);
        }
    }

    /**
     * 判断数组是否与现有结果重复且满足条件，如果是则存入结果。
     *
     * @param ints 要保存的数组
     */
    private static void saveResult(int[] ints) {
        boolean exists = false;

        for (int[] result : results) {
            if (same(result, ints)) {
                exists = true;
                break;
            }
        }

        if (!exists && available(ints)) {
            results.add(ints);
        }
    }

    /**
     * 比较两个数组是否完全相同
     *
     * @param a 一个数组
     * @param b 另一个数组
     *
     * @return 如果数组中每个元素都相同，则返回 true。
     */
    private static boolean same(int[] a, int[] b) {
        boolean same = true;
        for (int i = 0; i < a.length; i++) {
            if (a[i] != b[i]) {
                same = false;
                break;
            }
        }
        return same;
    }

    /**
     * 输出数组
     *
     * @param ints 要输出的数组
     */
    private static void printArr(int[] ints) {
        for (int n : ints) {
            System.out.print(n + " ");
        }
        System.out.println();
    }

    /**
     * 检查数组是否符合要求
     *
     * @param ints 要检查的数组
     *
     * @return 如果 4 在第三位，或者 3 和 5 相连，则返回 false。
     */
    private static boolean available(int[] ints) {
        return ints[2] != 4 && (Math.abs(indexOf(ints, 3) - indexOf(ints, 5)) > 1);
    }

    /**
     * 查找指定数字在数组中的位置
     *
     * @param ints 指定数组
     * @param n    指定数字
     *
     * @return 指定数字在数组中的位置。如果找不到，则返回 -1。
     */
    private static int indexOf(int[] ints, int n) {
        for (int i = 0; i < ints.length; i++) {
            if (ints[i] == n) {
                return i;
            }
        }
        return -1;
    }
}

输出结果：

java 代码

1 2 2 3 4 5
1 2 2 5 4 3
1 2 3 2 4 5
1 2 3 2 5 4
1 2 3 4 2 5
1 2 3 4 5 2
1 2 5 4 3 2
......
5 1 2 2 4 3
5 1 2 2 3 4
5 1 3 2 4 2
5 1 3 2 2 4
5 1 3 4 2 2
结果数量：198