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

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

（查看完整输出）

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

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

感谢@polygenelubricants 提供了出色的解决方案。
这是 Javascript 的等价内容：

var a=['0'];

var b=['Auto', 'Home'];

var c=['Good'];

var d=['Tommy', 'Hilfiger', '*'];

var attrs = [a, b, c, d];

function recurse (s, attrs, k) {
    if(k==attrs.length) {
        console.log(s);
    } else {
        for(var i=0; i<attrs[k].length;i++) {
            recurse(s+attrs[k][i], attrs, k+1);
        }
    } 
}
recurse('', attrs, 0);

Answer 3

编辑：这是一个红宝石解决方案。它与我下面的其他解决方案几乎相同，但假设您的输入字符数组是单词：因此您可以输入：

% perm.rb ruby is cool

~/bin/perm.rb

#!/usr/bin/env ruby

def perm(args)
  peg = Hash[args.collect {|v| [v,0]}]

  nperms= 1
  args.each { |a| nperms  *=  a.length }

  perms = Array.new(nperms, "")

  nperms.times do |p|
    args.each { |a| perms[p] += a[peg[a]] }

    args.each do |a|
      peg[a] += 1
      break  if peg[a] < a.length
      peg[a] = 0
    end

  end
  perms
end

puts perm ARGV

OLD - 我有在 MEL（Maya 的嵌入式语言）中执行此操作的脚本 - 我将尝试翻译为类似 C 的语言，但不要指望它无需进行任何修复即可运行；）但它可以在 Maya 中运行。

首先 - 将所有数组放在一个带有分隔符的长数组中。 （我将把它留给你 - 因为在我的系统中它会从 UI 中删除值）。因此，这意味着分隔符将占用额外的插槽： 要使用上面的示例数据：

 string delimitedArray[] = {"X","Y","Z","|","A","B","|","1","2","3","4","|"};

当然，您可以根据需要连接任意数量的数组。

string[] getPerms( string delimitedArray[]) {

    string result[];
    string delimiter("|");
    string compactArray[]; // will be the same as delimitedArray, but without the "|" delimiters
    int arraySizes[]; // will hold number of vals for each array
    int offsets[]; // offsets will holds the indices where each new array starts.
    int counters[]; // the values that will increment in the following loops, like pegs in each array

    int nPemutations = 1; 
    int arrSize, offset, nArrays;

    // do a prepass to find some information about the structure, and to build the compact array
    for (s in delimitedArray) {
        if (s == delimiter) { 
            nPemutations *= arrSize; // arrSize will have been counting elements 
            arraySizes[nArrays] = arrSize; 
            counters[nArrays] = 0; // reset the counter
            nArrays ++; // nArrays goes up every time we find a new array
            offsets.append(offset - arrSize) ; //its here, at the end of an array that we store the offset of this array
            arrSize=0; 
        } else { // its one of the elements, not a delimiter
            compactArray.append(s);
            arrSize++;
            offset++;
        }       
    }

    // put a bail out here if you like
    if( nPemutations > 256) error("too many permutations " + nPemutations+". max is 256");


    // now figure out the permutations
    for (p=0;p<nPemutations;p++) {
        string perm ="";

        // In each array at the position of that array's counter
        for (i=0;i<nArrays ;i++) {
            int delimitedArrayIndex = counters[i] + offsets[i] ;
            // build the string
            perm += (compactArray[delimitedArrayIndex]);

        }
        result.append(perm);

        // the interesting bit
        // increment the array counters, but in fact the program
        // will only get to increment a counter if the previous counter
        // reached the end of its array, otherwise we break
        for (i = 0; i < nArrays; ++i) {
            counters[i] += 1;
            if (counters[i] < arraySizes[i])
                break;
            counters[i] = 0;
        }
    }

    return result;
}

Answer 4

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

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

这有道理吗？

Answer 5

听起来你已经差不多明白了。

如果您再放入一个数组，称之为 ArrayHolder ，它包含所有未知数量、未知长度的数组，该怎么办？然后，你只需要另一个循环，不是吗？