I'm reposting this because people found the last description to be too hard to follow.
- The data unit I'm working with is a pair of 2 numbers. The numbers can be any integer that is bigger than 0. Example:
[X, Y]
- The input is 2 arrays of these pairs, each array can have any length. Example:
A = {[1, 2], [3, 2], [5, 1]}
B = {[2, 3], [4, 5], [5, 3]}
- If I combine 2 pairs, one from each array, I get a new pair like this:
[X1, Y1] + [X2, Y2] = [X1 + X2, Y1 + Y2]
- The output is a result of all combinations between the elements of the 2 input's where each element is the "best" and is ordered as ascending by Y
What "best" means in this case is that given [X, Y]
,
- this pair would have the highest or equal to highest X compared to all the other pairs that might have the same Y Example:
[2, 2], [2, 2],
[1, 2]
- it cannot have an X equal or lower than the maximum of any other pair that has a lower Y Example:
[2, 1], [4, 2],
[2, 4]
To illustrate how the output can be reached
- Lets take this example input:
A = {[1, 2], [3, 2], [5, 1]}
B = {[2, 3], [4, 5], [5, 3]}
- First we combine every item in A with every item in B
A[1] + B[1] = [3, 5], A[1] + B[2] = [5, 7], A[1] + B[3] = [6, 5]
A[2] + B[1] = [5, 5], A[2] + B[2] = [7, 7], A[2] + B[3] = [8, 5]
A[3] + B[1] = [7, 4], A[3] + B[2] = [9, 6], A[3] + B[3] = [10, 4]
- Next we order the combinations by Y
[7, 4], [10, 4], [3, 5], [6, 5], [5, 5], [8, 5], [9, 6], [5, 7], [7, 7]
- Filter the combinations by the rules described above
[10, 4]
So in this example, the output is an array with the length of 1 because all other pairs with Y of 4 have lower X and all other pairs with Y > 4 have equal or lower X.
I didn't include it in the example because its not necessary but the process can be optimized by prefiltering A and B by the same rules.
Now to my problem: I'm not dealing with arrays with the length of 3 but rather several hundred and the input count isn't 2 but 5+, as you can imagine, this process can be nested like this:
result5 = process(process(process(process(A, B), C), D, E)
So in practice, the potential memory use is A.size * B.size * C.size * D.size * E.size
.. which is a lot more than fits in the 20something kB i have available.
What I'm looking for is an algorithm that will fetch me the same results, in the same order, one by one. The fetches will be sequential and will start from 0 so I think any algorithm that can produce all the results in the right order without sorting in the end can be modified for this. Does anybody know how this could be achieved?