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

Question

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

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

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], ... ]

Я бы продолжил рекурсию. Например, в быстром и грязном питоне,

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 справляется с работой лучше, как в этот вопрос .)

Answer 1

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

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

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

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

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

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

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

Answer 2

Поскольку вы просили решение, не зависящее от языка, здесь есть одно в 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 ...

Answer 3

Итерация от 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;  
    }
}

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

Answer 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;
  }
} 

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

Редактировать : ну, слишком поздно, наверное. По сути, это то же самое, что и подсчет, просто еще один взгляд на это.