当数组数量和每个数组的长度未知时生成字符组合的所有排列 [英] Generating All Permutations of Character Combinations when # of arrays and length of each array are unknown

问题描述

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

I'm not sure how to ask my question in a succinct way, so I'll start with examples and expand from there. I am working with VBA, but I think this problem is non language specific and would only require a bright mind that can provide a pseudo code framework. Thanks in advance for the help!

示例:我有 3 个这样的字符数组:

Example: I have 3 Character Arrays Like So:

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

我想像这样生成所有可能的字符数组排列:

I would like to generate ALL possible permutations of the character arrays like so:

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

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

This can be easily solved using 3 while loops or for loops. My question is how do I solve for this if the # of arrays is unknown and the length of each array is unknown?

以 4 个字符数组为例:

So as an example with 4 character arrays:

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 = [...]

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

Is there a way to structure a function that will generate an unknown number of loops and loop through the length of each array to generate the permutations? Or maybe there's a better way to think about the problem?

谢谢大家！

推荐答案

递归解决方案

这实际上是最简单、最直接的解决方案.以下是 Java 中的内容，但应该具有指导意义:

Recursive solution

This is actually the easiest, most straightforward solution. The following is in Java, but it should be instructive:

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 递归结束时.

Note: Java arrays are 0-based, so k goes from 0..arrs.length-1 during the recursion, until k == arrs.length when it's the end of recursion.

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

It's also possible to write a non-recursive solution, but frankly this is less intuitive. This is actually very similar to base conversion, e.g. from decimal to hexadecimal; it's a generalized form where each position have their own set of values.

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;
    }
}

(查看完整输出)

这会以不同的顺序生成连音.如果您想以与递归解决方案相同的顺序生成它们，那么您可以在 decode 期间向后"迭代 arrs ，如下所示:

This produces the tuplets in a different order. If you want to generate them in the same order as the recursive solution, then you iterate through arrs "backward" during decode as follows:

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;
}

(查看完整输出)

这篇关于当数组数量和每个数组的长度未知时生成字符组合的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！