Java中如何高效穷举两位以上数字的所有组合？

碧海醫心 2024-11-29 00:00:00 次阅读

如何在 java 中高效地穷举两位以上的所有组合方式

为了穷举出特定列表中两位以上的所有组合方式，可以利用 java 的递归算法和排列算法。

首先，通过递归函数 combine 产生所有可能的子组合。它接受原始列表和一个临时列表作为参数。递归会从最短的组合长度开始，逐渐增加组合长度。

在递归中，调用排列函数 permutation 来排列每个子组合，从而生成所有可能的组合。排列算法将临时列表中的元素重新排列，然后将重排后的元素打印出来。

以下 java 代码展示了如何实现此算法：

import java.util.*;

public class Test {

    // 使用递归实现
    public static void main(String[] args) {
        int[] nums = { 11, 33, 22 };
        for (int i = 2; i <= nums.length; i++) {
            combine(nums, new int[i], 0, 0);
        }
    }

    public static void combine(int[] nums, int[] temp, int start, int index) {
        if (index == temp.length) {
            permutation(temp, 0, temp.length - 1);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            temp[index] = nums[i];
            combine(nums, temp, i + 1, index + 1);
        }
    }

    public static void permutation(int[] arr, int start, int end) {
        if (start == end) {
            System.out.println(Arrays.toString(arr));
        } else {
            for (int i = start; i <= end; i++) {
                swap(arr, start, i);
                permutation(arr, start + 1, end);
                swap(arr, start, i);
            }
        }
    }

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