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

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