#include <iostream>
#include <vector>
void cartesian (std::vector<std::vector<int>> const& items) {
auto n = items.size();
auto next = [&](std::vector<int> & x) {
for ( int i = 0; i < n; ++ i )
if ( ++x[i] == items[i].size() ) x[i] = 0;
else return true;
return false;
};
auto print = [&](std::vector<int> const& x) {
for ( int i = 0; i < n; ++ i )
std::cout << items[i][x[i]] << ",";
std::cout << "\b \n";
};
std::vector<int> x(n);
do print(x); while (next(x)); // Shazam!
}
int main () {
std::vector<std::vector<int>>
items { { 1, 2, 3 }, { 4, 5 }, { 6, 7, 8 } };
cartesian(items);
return 0;
}
Идея этого заключается в следующем.
Пусть n := items.size().
Пусть m_i := items[i].size(), для всех i в {0,1,...,n-1}.
Пусть M := {0,1,...,m_0-1} x {0,1,...,m_1-1} x ... x {0,1,...,m_{n-1}-1}.
Сначала мы решим более простую задачу итерации по M. Это достигается с помощью next лямбды. Алгоритм - это просто «несущие» обычные школьники, которые используют для сложения 1, хотя и со смешанной системой счисления.
Мы используем это для решения более общей проблемы путем преобразования кортежа x в M в один из желаемых кортежей по формуле items[i][x[i]] для всех i в {0,1,...,n-1}. Мы выполняем это преобразование в print лямбду.
Затем мы выполняем итерацию с do print(x); while (next(x));.
Теперь несколько комментариев о сложности, при условии, что m_i > 1 для всех i:
- Этот алгоритм требует
O(n) пробела. Обратите внимание, что явное построение декартового произведения занимает O(m_0 m_1 m_2 ... m_{n-1}) >= O(2^n) места. Таким образом, это экспоненциально лучше в пространстве, чем любой алгоритм, который требует, чтобы все кортежи хранились одновременно в памяти.
- Функция
next принимает амортизированное время O(1) (по аргументу геометрической серии).
- Функция
print занимает O(n) время.
- Следовательно, в целом алгоритм имеет временную сложность
O(n|M|) и пространственную сложность O(n) (не считая затрат на хранение items).
Интересно отметить, что если заменить print функцией, которая проверяет в среднем только O(1) координаты на кортеж, а не все из них, то временная сложность падает до O(|M|), то есть становится линейное время по отношению к размеру декартового произведения. Другими словами, избегание копирования кортежа для каждой итерации может иметь смысл в некоторых ситуациях.