Java获得一个数组的指定长度排列组合算法示例

发布时间：2024/03/08

下面详细讲解一下Java获得一个数组的指定长度排列组合算法示例的完整攻略。

算法说明

在程序设计中，经常会遇到需要从给定的元素集合中去选取一些元素，这些元素能组成的各种可能长度的排列和组合集合。这时候，排列和组合问题就变得特别重要。在Java中，提供了一些工具类帮助我们解决这些问题。

排列和组合的定义

排列问题中，给定n个元素，从中选取k个元素进行排列，若n个元素都用上，排列结果为n!，若没有全部用上，排列的结果就为n(n-1)(n-2)……(n-k+1)

组合问题中，给定n个元素，从中选取k个元素进行组合，而k个元素的顺序不再是关注点，因此总的组合结果数就是C(n,k) = n! / (k!(n-k)!).

代码实现

下面是Java实现获取一个数组的指定长度排列和组合的示例：

import java.util.ArrayList;
import java.util.Arrays;

public class CombinationPermutation {
    /**
     * 组合算法
     *
     * @param ori      原数据集合
     * @param isRepeat 是否可重复取数
     * @param result   存储结果集的集合
     * @param begin    取数的起始下标
     * @param arr      临时存储已取数的数组
     * @param count    要取的数的个数
     */
    private static void combinationAlgorithm(int[] ori, boolean isRepeat, ArrayList<ArrayList<Integer>> result, Integer begin, Integer[] arr, int count) {
        if (count == 0) {
            result.add(new ArrayList<>(Arrays.asList(arr)));
            return;
        }
        for (int i = begin; i < ori.length; i++) {
            if (!isRepeat && i > begin && ori[i] == ori[i - 1]) {
                continue;
            }
            arr[arr.length - count] = new Integer(ori[i]);
            combinationAlgorithm(ori, isRepeat, result, i + 1, arr, count - 1);
        }
    }

    /**
     * 输入原数组，指定长度，获取所有组合数
     *
     * @param ori 原数据数组
     * @param len 指定的长度
     * @return 所有组合数
     */
    public static ArrayList<ArrayList<Integer>> getCombination(int[] ori, int len) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (ori == null || ori.length == 0 || ori.length < len || len < 1) {
            return result;
        }
        boolean isRepeat = false;
        Integer[] arr = new Integer[len];
        Arrays.sort(ori);
        combinationAlgorithm(ori, isRepeat, result, 0, arr, len);
        return result;
    }

    /**
     * 排列算法
     *
     * @param ori      原数组
     * @param isRepeat 是否可重复取数
     * @param result   存储结果集的ArrayList
     * @param arr      临时存储已经取出的数的数组
     * @param used     用来标记数字在当前排列中是否已经出现
     */
    private static void permutationAlgorithm(int[] ori, boolean isRepeat, ArrayList<ArrayList<Integer>> result, Integer[] arr, boolean[] used) {
        if (arr.length == ori.length) {
            result.add(new ArrayList<>(Arrays.asList(arr)));
            return;
        }
        for (int i = 0; i < ori.length; i++) {
            if (!isRepeat && used[i]) {
                continue;
            }
            if (isRepeat || (!isRepeat && (i == 0 || ori[i] != ori[i - 1] || used[i - 1]))) {
                arr[arr.length - ori.length + i] = new Integer(ori[i]);
                boolean[] tmpUsed = new boolean[used.length];
                System.arraycopy(used, 0, tmpUsed, 0, used.length);
                if (!isRepeat) {
                    //当前排列已包含该数字，将used设置为true，表示在接下来的递归中不能再使用这个数字
                    tmpUsed[i] = true;
                }
                permutationAlgorithm(ori, isRepeat, result, arr, tmpUsed);
            }
        }
    }

    /**
     * 输入原数组，指定长度，获取所有排列数
     *
     * @param ori 原数据数组
     * @param len 指定长度
     * @return 所有排列数
     */
    public static ArrayList<ArrayList<Integer>> getPermutation(int[] ori, int len) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (ori == null || ori.length == 0 || ori.length < len || len < 1) {
            return result;
        }
        boolean isRepeat = false;
        Integer[] arr = new Integer[len];
        boolean[] used = new boolean[ori.length];
        Arrays.sort(ori);
        permutationAlgorithm(ori, isRepeat, result, arr, used);
        return result;
    }

    public static void main(String[] args) {
        int[] ori = {1, 2, 3, 3};
        ArrayList<ArrayList<Integer>> combinationResult = getCombination(ori, 2);
        ArrayList<ArrayList<Integer>> permutationResult = getPermutation(ori, 2);
        System.out.println("数组 " + Arrays.toString(ori) + " 中选取 2 个数字的所有组合：");
        System.out.println(combinationResult.toString());
        System.out.println("数组 " + Arrays.toString(ori) + " 中选取 2 个数字的所有排列：");
        System.out.println(permutationResult.toString());
    }
}

注释中已经详细解释了排列和组合算法的实现过程，以及以上代码的实现方式。上面的代码中，针对组合和排列分别对应了getCombination和getPermutation方法，其中

getCombination方法输入原数组和指定长度，返回一个ArrayList，包含了所有的组合结果
getPermutation方法输入原数组和指定长度，返回一个ArrayList，包含了所有的排列结果

在实现时，以上两个方法都是通过类似DFS的递归方式实现，通过记录已经使用的数字，避免产生重复结果。

示例说明

针对以上算法，下面通过两个示例来说明排列和组合的生成过程：

示例1：从数组[1,2,3,3] 中选取2个数字的所有组合

下面是执行结果：

数组 [1, 2, 3, 3] 中选取 2 个数字的所有组合：
[[1, 2], [1, 3], [1, 3], [2, 3], [2, 3], [3, 3]]

结果中可以看到，选择 2 个数字进行组合，共有6个答案，其包括：[1,2]、[1,3]、[1,3]、[2,3]、[2,3]、[3,3]。

示例2：从数组[1,2,3,3]中选取2个数字的所有排列

下面是执行结果：

数组 [1, 2, 3, 3] 中选取 2 个数字的所有排列：
[[1, 2], [1, 3], [1, 3], [2, 1], [2, 3], [2, 3], [3, 1], [3, 2], [3, 3], [3, 1], [3, 2], [3, 3]]

结果中可以看到，选择两个数字进行排列，共有12个答案，其包括：[1,2]、[1,3]、[1,3]、[2,1]、[2,3]、[2,3]、[3,1]、[3,2]、[3,3]、[3,1]、[3,2]、[3,3]。

至此，我们已经详细讲解了Java获得一个数组的指定长度排列组合算法的完整攻略，希望这里的示例和说明对你有所帮助。