Есть задача: имеется произвольное кол-во массивов цен (представленных BigDecimal) в кол-ве от 1 до 100. Цены во всех массивах отсортированы в порядке возрастания. Массивы могут содержать разное кол-во элементов, минимум 1, максимум 100. Каждый массив может содержать одинаковые цены. Необходимо получить итератор, который последовательно переберет декартово произведение всех этих массивов. При этом элементы декартового произведения (т.е. кортежи) должны перебираться в порядке не убывания сумм их элементов (если несколько кортежей имеют одинаковую сумму - их можно выдать в любом порядке).
Пример:
- Исходные массивы [1,2], [10,100], [10, 20].
- Итератор должен выдать следующую последовательность:
- [1,10,10] | (сумма = 21) | кортеж индексов [0,0,0]
- [2,10,10] | (сумма = 22) | кортеж индексов [1,0,0]
- [1,10,20] | (сумма = 31) | кортеж индексов [0,0,1]
- [2,10,20] | (сумма = 32) | кортеж индексов [1,0,1]
- [1,100,10] | (сумма = 111) | кортеж индексов [0,1,0]
- [2,100,10] | (сумма = 112) | кортеж индексов [1,1,0]
- [1,100,20] | (сумма = 121) | кортеж индексов [0,1,1]
- [2,100,20] | (сумма = 122) | кортеж индексов [1,1,1]
Как именно происходит обращение к результатам работы алгоритма:
Пользователь(не обязательно человек) запрашивает данные порциями в размере от 1_000 до 10_000 элементов. Между запросами интервал в 1-2 секунды. Пример, пользователь запрашивает сперва первые 10_000 элементов, потом спустя секунду - следующие после них 10_000 элементов и т.д.
Ограничения:
Время получения каждого следующего элемента последовательности не должно превышать 0.05 секунды, объем памяти используемый алгоритмом не должен превышать 20 мб.
Вот до чего я пока смог додуматься:
- Это задача связана с графами, скорее всего - с алгоритмом Дейкстры.
- Вершинами графа будут выступать кортежи индексов.
- Каждой вершине графа назначен вес равный сумме элементов массивов, на которые ссылается кортеж индексов представляющий эту вершину. Так первый индекс кортежа ссылается на элемент под этим индексом в первом массиве, второй индекс кортежа ссылается на элемент под этим индексом во втором массиве и т.д.
- Т.к. мы можем двигаться только к вершинам с большим или равным весом, то граф является ориентированным.
- Если хотя бы один индекс кортежа А меньше соответствующего индекса кортежа В, а остальные индексы попарно равны - то вес вершины А меньше или равен весу вершины В.
- Число смежных вершин каждой рассматриваемой вершины не превышает кол-во элементов кортежа представляющего данную вершину. Это обусловлено тем, что при поиске следующей вершины с большим весом относительно текущей - мы просматриваем те вершины, у которых один из индексов больше на единицу соответствующего индекса текущей вершины, а остальные индексы попарно равны.
- Исходя из пунктов 2 - 6 имеем область N-мерного пространства(где N - число массивов цен) ограниченную гиперкубом со сторонами равными размерам соответствующих массивов. Внутри этой области имеется ориентированный взвешенный граф вершинами которого выступают все точки этой области имеющие целочисленные координаты. Каждой вершине назначен вес (как описано в пункте 3).
В чем нужна помощь: у меня не получается найти подход к решению данной задачи, который позволил бы уложиться в заданные ограничения.