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

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

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

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

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

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


iteration algorithm cartesian-product language-agnostic
person Federico A. Ramponi    schedule 10.03.2010    source источник

Ответы (4)


arrow_upward
18
arrow_downward

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

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

person Mark Byers    schedule 10.03.2010
comment
Ага. Довольно легко действительно. Спасибо. - person Federico A. Ramponi; 10.03.2010
comment
Я думаю, что ваш код на самом деле немного более неэффективен, чем ваш алгоритм.. ;P - person Larry; 10.03.2010
comment
Да... у меня есть другая версия, которая точно соответствует алгоритму, но, на мой взгляд, она довольно запутанная! Может все таки выложу... - person Mark Byers; 10.03.2010
comment
@Larry: я тоже опубликовал свою первую версию! Может быть, это можно было бы написать более аккуратно, но это работает... - person Mark Byers; 10.03.2010
comment
=) Просто говорю, потому что когда я представил свой ответ и увидел ваш, а ваш явно эффективнее! - person Larry; 10.03.2010
comment
Однако решение, использующее трюк по модулю, увеличивается с первого элемента. - person norok2; 21.03.2020

arrow_upward
3
arrow_downward

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

arrow_upward
2
arrow_downward

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

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

person Larry    schedule 10.03.2010

arrow_upward
1
arrow_downward

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

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

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

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

person IVlad    schedule 10.03.2010