高效的Java版排列组合算法

前言

排列组合是数学中的一种常见问题，例如给定数列[1,2,3]，对其进行排列组合可以得到以下六种可能：

• 1 2 3
• 1 3 2
• 2 1 3
• 2 3 1
• 3 1 2
• 3 2 1

在Java中，我们可以使用递归和循环等方式来实现排列组合，但是如果数列过长，将会十分耗时，因此我们需要一种高效的实现方式。

算法基础

排列

排列的基本概念是：一组数据中，任意取出几个（也可以是全部），按照一定的顺序排列起来，叫做这组数据的一个排列。

在Java中，我们可以通过递归函数来生成排列。

public static void permutation(int[] nums, int start, List<List<Integer>> res) {
    if (start >= nums.length) {
        List<Integer> list = new ArrayList<>();
        for (int n : nums) {
            list.add(n);
        }
        res.add(list);
    } else {
        for (int i = start; i < nums.length; i++) {
            swap(nums, i, start);
            permutation(nums, start + 1, res);
            swap(nums, i, start);
        }
    }
}

private static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

上面的递归函数permutation接收一个整数数组nums，一个整数start和一个List> res，表示从nums[start]开始生成一个排列，并将结果保存在res中。我们先将nums[start]与nums[start+1]到nums[nums.length-1]依次交换，然后递归调用函数permutation，直到start >= nums.length。

组合

组合的基本概念是：一组数据中，任意取出几个（不能重复取出），不考虑顺序排列起来，叫做这组数据的一个组合。

在Java中，我们可以通过递归函数来生成组合。

public static void combination(int[] nums, int start, int k, List<List<Integer>> res) {
    if (k == 0) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if ((start & (1 << i)) != 0) {
                list.add(nums[i]);
            }
        }
        res.add(list);
    } else {
        for (int i = start; i < (1 << nums.length); i++) {
            if (Integer.bitCount(i) != k) {
                continue;
            }
            combination(nums, i + 1, k - 1, res);
        }
    }
}

上面的递归函数combination接收一个整数数组nums，一个整数start，一个整数k和一个List> res，表示从nums[start]开始选择k个数，生成一个组合，并将结果保存在res中。我们通过循环枚举[0,2^nums.length)范围内的数，如果这个数中1的个数不等于k，说明选中的数个数不足k个，因此直接跳过。否则，递归调用combination函数，将选中的数添加到结果中。

算法优化

虽然上面的排列组合算法已经可以完成任务，但是在处理长数列的时候，时间开销仍然很大。我们可以通过剪枝和非递归方式等方式优化算法，以提高算法效率。

排列算法优化

剪枝：在对nums数组进行交换的时候，可以首先检查当前元素是否与之前交换过，避免重复计算。

非递归方式：使用while循环代替递归实现，只需要保存下标，因此实现简单，效率高。

public static List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    int n = nums.length;
    int[] indexes = new int[n];
    for (int i = 0; i < n; i++) {
        indexes[i] = 0;
    }
    int i = 0;
    while (i < n) {
        if (indexes[i] < i) {
            swap(nums, i % 2 == 0 ? 0 : indexes[i], i);
            List<Integer> list = new ArrayList<>();
            for (int num : nums) {
                list.add(num);
            }
            res.add(list);
            indexes[i]++;
            i = 0;
        } else {
            indexes[i] = 0;
            i++;
        }
    }
    return res;
}

组合算法优化

剪枝：组合算法本身就包含了去重的操作，因此不需要再进行剪枝。

非递归方式：使用while循环代替递归实现，只需要保存下标，因此实现简单，效率高。

public static List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<>();
    if (n < k || n == 0) {
        return res;
    }
    int[] indexes = new int[k];
    for (int i = 0; i < k; i++) {
        indexes[i] = i;
    }
    while (indexes[0] < n - k + 1) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            list.add(indexes[i] + 1);
        }
        res.add(list);
        int t = k - 1;
        while (t >= 0 && indexes[t] == n - k + t) {
            t--;
        }
        if (t < 0) {
            break;
        }
        indexes[t]++;
        for (int i = t + 1; i < k; i++) {
            indexes[i] = indexes[i - 1] + 1;
        }
    }
    return res;
}

示例说明

下面是一个排列的例子，[1,2,3,4,5,6,7,8,9,10]这样一个长度为10的数列，我们需要从中生成其全部的排列组合。可以使用上面所介绍的算法进行计算。

int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
List<List<Integer>> permutations = permute(nums);
List<List<Integer>> combinations = combine(10, 5);

通过使用上面的代码，我们可以得到nums的所有排列和长度为5的所有组合。

结语

排列组合算法是程序设计中常见的问题，通过使用Java中的递归和非递归方式，可以实现高效的排列组合算法。本篇文章介绍了基础的排列组合算法，以及如何通过剪枝和非递归方式等方式优化算法。