Как я могу вычислить декартово произведение итеративно?

Этот вопрос спрашивает, как вычислить декартово произведение заданного числа векторов. Так как число векторов известно заранее и довольно мало, решение легко получается с вложенными циклами.

Теперь предположим, что вам предоставляется на вашем языке выбора вектор векторов (или список списков или набор наборов и т.д.):

l = [ [1,2,3], [4,5], [6,7], [8,9,10], [11,12], [13] ]

Если бы меня попросили вычислить его декартово произведение, то есть

[ [1,4,6,8,11,13], [1,4,6,8,12,13], [1,4,6,9,11,13], [1,4,6,9,12,13], ... ]

Я бы продолжил рекурсию. Например, в quick & dirty python,

def cartesianProduct(aListOfLists):
    if not aListOfLists:
        yield []
    else:
        for item in aListOfLists[0]:
            for product in cartesianProduct(aListOfLists[1:]):
                yield [item] + product

Есть ли простой способ вычислить его итеративно?

(Примечание. Ответ не обязательно должен быть в python, и в любом случае я знаю, что в python itertools делает работу лучше, чем в этот вопрос.)

Ответы

Ответ 1

1) Создайте список индексов в соответствующие списки, инициализированные до 0, i.e:

indexes = [0,0,0,0,0,0]

2) Выведите соответствующий элемент из каждого списка (в этом случае первый).

3) Увеличьте последний индекс на единицу.

4) Если последний индекс равен длине последнего списка, reset он равен нулю и нести один. Повторяйте это до тех пор, пока не будет проведена переноска.

5) Вернитесь к шагу 2, пока индексы не вернутся к [0,0,0,0,0,0]

Это похоже на то, как работает подсчет, за исключением базы для каждой цифры.

Здесь реализация вышеуказанного алгоритма в Python:

def cartesian_product(aListOfList):
    indexes = [0] * len(aListOfList)
    while True:
        yield [l[i] for l,i in zip(aListOfList, indexes)]
        j = len(indexes) - 1
        while True:
            indexes[j] += 1
            if indexes[j] < len(aListOfList[j]): break
            indexes[j] = 0
            j -= 1
            if j < 0: return

Вот еще один способ реализовать его с помощью модульных трюков:

def cartesian_product(aListOfList):
    i = 0
    while True:
        result = []
        j = i
        for l in aListOfList:
             result.append(l[j % len(l)])
             j /= len(l)
        if j > 0: return
        yield result
        i += 1

Обратите внимание, что это приводит к результатам в несколько другом порядке, чем в вашем примере. Это можно устранить, итерации по спискам в обратном порядке.

Ответ 2

Итерация от 0 до \Pi a_i_length для всех i.

for ( int i = 0; i < product; i++ ) {
    // N is the number of lists
    int now = i;
    for ( int j = 0; j < N; j++ ) {
        // This is actually the index, you can get the value easily.
        current_list[j] = now % master_list[j].length;

        // shifts digit (integer division)
        now /= master_list[j].length;  
    }
}

Есть также некоторые тривиальные способы написать это, поэтому вам не нужно выполнять одну и ту же работу дважды.

Ответ 3

Поскольку вы запрашивали языковое агностическое решение, вот один из bash, но можем ли мы назвать его итеративным, рекурсивным, что это такое? Это просто обозначение:

echo {1,2,3},{4,5},{6,7},{8,9,10},{11,12},13

может быть достаточно интересным.

1,4,6,8,11,13 1,4,6,8,12,13 1,4,6,9,11,13 1,4,6,9,12,13 1,4,6,10,11,13 ...

Ответ 4

Вам просто нужно управлять своим стеком вручную. В основном, делайте то, что рекурсия делает сама по себе. Поскольку рекурсия помещает данные о каждом рекурсивном вызове в стек, вы просто делаете то же самое:

Let L[i] = elements in vector i
k = 0;
st[] = a pseudo-stack initialized with 0
N = number of vectors 
while ( k > -1 )
{
  if ( k == N ) // solution, print st and --k

  if ( st[k] < L[k].count )
  {
    ++st[k]
    ++k
  }
  else
  {
    st[k] = 0;
    --k;
  }
}

Не тестировалось, но идея будет работать. Надеюсь, я ничего не пропустил.

Изменить: ну, слишком поздно, я думаю. Это в основном то же самое, что и подсчет, это еще один способ взглянуть на него.