CODEWITHSUNDEEP
algorithmpermutation
Richard
Richard

Reputation: 15562

On algorithm of iterating an array of arrays

there are n arrays a_0, ..., a_n-1, each of l elements. how to write efficient code to iterate all combinations, in which each element is picked from a distinct array. for example, if two arrays are [0, 1] and [3, 4], then the output should be

[0, 3]
[0, 4]
[1, 3]
[1, 4]

Upvotes: 2

Views: 123

Answers (2)

PengOne
PengOne

Reputation: 48398

You cannot do better than O(l^n), as nightcracker correctly points out. Here's one way that you can approach the problem.

Make a large array A whose ith entry is the array a_i, i.e.

A[i] = a_i

Now iterate through all words of length n on the alphabet {0,1,...,l}:

-(array*)nextWord:(array*)word {
    array *newWord = word;
    for (int i=n-1; i=>0; ++i) {
        if (word[i] < l) {
            newWord[i] = word[i]+1;
            for (int j=i+1; j<n; ++j) {
                newWord[i] = 0;
            }
            return newWord;
        }
    }
    return NULL;
}

Finally, select the entries based on the word by 

word = [0, 0, ... , 0];
while (word != NULL) {
    A[0][word[0]], A[1][word[1]], ... , A[n-1][word[n-1]];
    word = nextWord(word);
}

Sorry for the inconsistencies in the pseudocode, but hopefully you can discern the logic here.

Incidentally, based on the example in the question, I am assuming that the first entry should come from the first array, the second entry from the second array, and so on. If this is not the case, then you can still use the idea above and then permute the entries. However, doing this may lead to repetitions if and only if two of the arrays have a common entry.

Upvotes: 1

orlp
orlp

Reputation: 117711

In an ideal mathematical environment there is no better algorithm then O(l^n), you are going to produce an output of l^n elements anyway.

If you give us context like programming language or architecture we can think of the algorithm closest to O(l^n).

Upvotes: 3

Related Questions