Generating All Permutations of Character Combinations when # of arrays and length of each array are unknown

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!

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

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?

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]

I would need to generate:

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

So the Generalized Example would be:

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?

Thanks Everyone!

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

(see full output)

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.

Non-recursive solution

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

(see full output)

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

(see full output)

Thanks to @polygenelubricants for the excellent solution. Here is the Javascript equivalent:

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

EDIT: Here's a ruby solution. Its pretty much the same as my other solution below, but assumes your input character arrays are words: So you can type:

% 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 - I have a script to do this in MEL, (Maya's Embedded Language) - I'll try to translate to something C like, but don't expect it to run without a bit of fixing;) It works in Maya though.

First - throw all the arrays together in one long array with delimiters. (I'll leave that to you - because in my system it rips the values out of a UI). So, this means the delimiters will be taking up extra slots: To use your sample data above:

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

Of course you can concatenate as many arrays as you like.

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

If I understand the question correctly, I think you could put all your arrays into another array, thereby creating a jagged array.

Then, loop through all the arrays in your jagged array creating all the permutations you need.

Does that make sense?

it sounds like you've almost got it figured out already.

What if you put in there one more array, call it, say ArrayHolder , that holds all of your unknown number of arrays of unknown length. Then, you just need another loop, no?