Об алгоритме итерации массива массивов

Question

есть n массивы a_0, ..., a_n-1, каждый из l элементов. Как написать эффективный код для итерации всех комбинаций, в которых каждый элемент выбирается из отдельного массива. например, если два массива - [0, 1] и [3, 4], то результат должен быть

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

Answer 1

В идеальной математической среде нет лучшего алгоритма, чем O (l ^ n), вы все равно будете производить вывод l ^ n элементов.

Если вы дадите нам контекст, такой как язык программирования илиАрхитектура, мы можем думать о алгоритме, ближайшем к O (l ^ n).

Answer 2

Вы не можете сделать лучше, чем O(l^n), как правильно указывает ночной взломщик. Вот один из способов, которым вы можете подойти к проблеме.

Создайте большой массив A, чья i -я запись - это массив a_i, т.е.

A[i] = a_i

Теперь перебираем все слова длины n в алфавите {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;
}

Наконец, выберите записи, основанные на слове, по

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

Извините за несоответствия в псевдокоде, но, надеюсь, вы сможете увидеть здесь логику.

---

Между прочим, исходя из примера в вопросе, я предполагаю, что первая запись должна исходить из первого массива, вторая запись из второго массива и так далее. Если это не так, то вы все равно можете использовать идею выше, а затем переставить записи. Однако выполнение этого может привести к повторениям в том и только в том случае, если два массива имеют общую запись.