当数组的数量和每个数组的长度未知时,生成字符组合的所有排列

Question

我不确定如何以简洁的方式提出我的问题,所以我将从示例开始并从那里扩展.我正在使用VBA,但我认为这个问题是非语言特定的,只需要一个可以提供伪代码框架的聪明头脑.在此先感谢您的帮助!

示例:我有3个字符数组,如此:

Arr_1 = [X,Y,Z] 
Arr_2 = [A,B]
Arr_3 = [1,2,3,4]

我想生成所有可能的字符数组排列,如下所示:

XA1
XA2
XA3
XA4
XB1
XB2
XB3
XB4
YA1
YA2
.
.
.
ZB3
ZB4

这可以使用3 while循环或for循环轻松解决.我的问题是,如果数组的数量未知且每个数组的长度未知,我该如何解决这个问题？

所以作为4个字符数组的例子:

Arr_1 = [X,Y,Z]
Arr_2 = [A,B]
Arr_3 = [1,2,3,4]
Arr_4 = [a,b]

我需要生成:

XA1a
XA1b
XA2a
XA2b
XA3a
XA3b
XA4a
XA4b
.
.
.
ZB4a
ZB4b  

所以广义的例子是:

Arr_1 = [...]
Arr_2 = [...]
Arr_3 = [...]
.
.
.
Arr_x = [...]

有没有办法构造一个函数,它将生成一个未知数量的循环并循环遍历每个数组的长度以生成排列？或者也许有更好的方法来思考这个问题？

感谢大家!

Answer 1

递归解决方案

这实际上是最简单,最直接的解决方案.以下是Java,但它应该是有益的:

public class Main {
    public static void main(String[] args) {
        Object[][] arrs = {
            { "X", "Y", "Z" },
            { "A", "B" },
            { "1", "2" },
        };
        recurse("", arrs, 0);
    }
    static void recurse (String s, Object[][] arrs, int k) {
        if (k == arrs.length) {
            System.out.println(s);
        } else {
            for (Object o : arrs[k]) {
                recurse(s + o, arrs, k + 1);
            }
        }
    }
}

(见完整输出)

注意:Java数组是基于0的,因此k从0..arrs.length-1递归期间开始,直到k == arrs.length递归结束.

非递归解决方案

编写非递归解决方案也是可能的,但坦率地说这不太直观.这实际上与基本转换非常相似,例如从十进制到十六进制; 它是一种通用形式,每个位置都有自己的一组值.

public class Main {
    public static void main(String[] args) {
        Object[][] arrs = {
            { "X", "Y", "Z" },
            { "A", "B" },
            { "1", "2" },
        };
        int N = 1;
        for (Object[] arr : arrs) {
            N = N * arr.length;
        }
        for (int v = 0; v < N; v++) {
            System.out.println(decode(arrs, v));
        }
    }
    static String decode(Object[][] arrs, int v) {
        String s = "";
        for (Object[] arr : arrs) {
            int M = arr.length;
            s = s + arr[v % M];
            v = v / M;
        }
        return s;
    }
}

(见完整输出)

这会以不同的顺序生成连音符.如果您想以与递归解决方案相同的顺序生成它们,那么您将按如下方式arrs"向后" 迭代decode:

static String decode(Object[][] arrs, int v) {
    String s = "";
    for (int i = arrs.length - 1; i >= 0; i--) {
        int Ni = arrs[i].length;
        s = arrs[i][v % Ni] + s;
        v = v / Ni;
    }
    return s;
}

(见完整输出)

Answer 2

如果我正确理解了这个问题，我认为您可以将所有数组放入另一个数组中，从而创建一个锯齿状数组。

然后，循环遍历锯齿状数组中的所有数组，创建所需的所有排列。

那有意义吗？