时间戳

首页 > 解决方案 > 遍历数字数组的每个排列

java - 遍历数字数组的每个排列

问题描述

我的问题是这样的：我在一个数组中有 n 个数字，每个都有一个最大值 m，我想遍历这些数字的每个排列，通过单独递增它们直到它们达到最大值。

一个例子：

[0,0,0,0]

Integer @ index 0 has a max value of 5
Integer @ index 1 has a max value of 3
Integer @ index 2 has a max value of 4
Integer @ index 3 has a max value of 6

Output: 
[0,0,0,1]
[0,0,0,2]
[0,0,0,3]
.
.
.
[0,1,1,0]
[0,1,1,1]
[0,1,1,2]
[0,1,1,3]
.
.
.
[5,0,2,1]
[5,0,2,2]
etc.

Python 有带有产品功能的 itertools，这可以解决我的问题，但它看起来不像 Java 有类似的东西。递归似乎是要走的路，但我可以找出前进的方向。

有谁知道如何实现上述输出？提前致谢 ：-）

标签： java

解决方案

从技术上讲，排列意味着某些元素的重新排序，例如，[3,1,2]是 的排列[1,2,3]。您所要求的等同于迭代笛卡尔积，因此 Python 函数被命名为product.

正如您正确指出的那样，递归是这里的方法。这是因为生成所有序列[5,3,4,6]需要生成所有序列，[3,4,6]开头为 0，然后再次以 1 开头，依此类推，直到 5。

import java.util.Arrays;

public class CartesianProduct {
    public static void main(String[] args) {
        printAll(5, 3, 4, 6);
    }

    public static void printAll(int... maxes) {
        int[] current = new int[maxes.length];
        printAll(maxes, current, 0);
    }

    private static void printAll(int[] maxes, int[] current, int i) {
        if(i == current.length) {
            System.out.println(Arrays.toString(current));
        } else {
            int max = maxes[i];
            for(int j = 0; j <= max; ++j) {
                current[i] = j;
                printAll(maxes, current, i+1);
            }
        }
    }
}

变量i是我们当前为其选择值的位置的索引，变量j是该位置的当前值，数组current保存当前序列。递归的基本情况是在所有地方都选择了值，所以我们打印。

推荐阅读