Как я могу вычислить Декартово произведение многократно?
Этот вопрос спрашивает, как вычислить Декартово произведение данного количества векторов. Так как количество векторов известно заранее и довольно маленькое, решение легко получено с вложенным для циклов.
Теперь предположите, что Вам дают, на Вашем предпочтительном языке, векторе векторов (или список списков или набор наборов, и т.д.):
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 делает задание лучше, как в этом вопросе.)
3 ответа
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
Обратите внимание, что это выводит результаты в несколько другом порядке, чем в вашем примере. Это можно исправить, перебирая списки в обратном порядке.
Вам просто нужно управлять своим стеком вручную. По сути, делайте то, что рекурсия делает самостоятельно. Поскольку рекурсия помещает данные о каждом рекурсивном вызове в стек, вы просто делаете то же самое:
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;
}
}
Не тестировалось, но идея будет работать. Надеюсь, я ничего не пропустил.
Править : ну, наверное, поздно. По сути, это то же самое, что и счет, только другой взгляд на это.
Итерация от 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;
}
}
Есть также несколько тривиальных способов записать это, чтобы не делать одну и ту же работу дважды.