algorithm - How can I find all of the permutations consisting of 1 element from a variable number of arrays of variable length?

Question

I have an array U of arrays D that vary in length. I need to be able to return all permutations of array indices that would select a different permutation consisting of 1 element from each set. I also require that this alorithm gets represented as an object that only remembers the last permutation, and returns the next permutation with a get_next method.

For instance, U = [array_of_size_n1, array_of_size_n2, array_of_size_n3] There would be n1*n2*n3 permutations, each 3 elements long.

Edit: the number of sets also varies.

Answer 1

If you're using python, this is part of the standard library: itertools.product. But assuming you're not, here's a pseudocode version.

// Create an initialised array of indexes.
int[] index0(arrays) {
    // We require all arrays to be non-empty.
    for a in arrays {
        assert len(a) != 0;
    }
    return new int[len(arrays)];
}

// Increment the indices. Returns false when the indices wrap round to the start.
bool next_index(indices, arrays) {
    for (i = len(indices) - 1; i >= 0; --i) {
        indices[i] += 1
        if indices[i] < len(arrays[i]) {
            return true;
        }
        indices[i] = 0;
    }
    return false;
}

You can use it like this (assuming none of your arrays are empty). This example prints out every combination of elements from the arrays.

indices = index0(arrays); 
{
    for (i = 0; i < len(arrays); ++i) {
        print arrays[i][indices[i]];
    }
    print
} while next_index(indices);