What elegant solution exists for this template? Multilevel search

Question

Suppose we have several arrays of integers. You can consider each array as a level. We try to find a sequence of elements, exactly one element from each array, and move on to the next array with the same predicate. For example, we have v1, v2, v3 as arrays:

 v1 | v2 | v3 ----------------- 1 | 4 | 16 2 | 5 | 81 3 | 16 | 100 4 | 64 | 121 

I could say that predicate: next_element == previous_element^2
The correct sequence from the above example is: 2 -> 4 -> 16
In fact, in this example there is no other valid sequence. I could write three loops to iterate over the above example, but what if the number of arrays is a variable , but of course you know the order, how would you solve this problem?

Tips or links to design patterns are very welcome. I will do it in C ++, but I just need an idea.

Thanks,

Answer 1

If you order your arrays in advance, the search can be done much faster. You can start with your smaller array, then binary-look for the expected numbers on each of them. This will be O (nklogM), n is the size of the smallest array, k is the number of arrays, M is the size of the largest array

This can be done even faster if you use Hashmaps instead of arrays. This will allow you to search in O (n * k).

If using inverse functions (to search in earlier arrays) is not an option, then you should start with the first array and n = the size of the first array.

For simplicity, I'll start with the first array

 //note the 1-based arrays for (i : 1 until allArrays[1].size()) { baseNumber = allArrays[1][i]; for (j: 2 until allArrays.size()) { expectedNumber = function(baseNumber); if (!find(expectedNumber, allArrays[j])) break; baseNumber = expectedNumber; } } 

You can probably do some null checks and add some logical lines there to find out if the sequence exists or not

Answer 2

(Design patterns are applied to the class and API design to improve the quality of the code, but they are not designed to solve computational problems.)

Depending on the cases:

• If arrays arrive at random and you have limited space, then brute force is the only solution. O (N ^k ) time (k = 3), O (1) space.
• If the predicate is not reversible (for example, SHA1(next_elem) xor SHA1(prev_elem) == 0x1234 ), then the only solution is also brute force.
• If you can waste space, then create hash sets for v2 and v3 so that you can quickly find the next element that satisfies the predicate. O (N + b ^k ), O (kN). (b = the maximum number next_elem that satisfies the predicate given prev_elem)
• If arrays are sorted and limited, you can also use binary search instead of a hash table to avoid using space. O (N (log N) ^k-1 + b ^k ) time, O (1) space.

(The entire number of spaces is not taken into account when using the stack due to recursion.)

A general method that consumes up to O (Nb ^k ) is to construct a solution by sequential filtering, for example

 solutions = [[1], [2], ... [N]] filterSolution (Predicate, curSols, nextElems) { nextSols = [] for each curSol in curSols: find elem in nextElems that satisfy the Predicate append elem into a copy of curSol, then push into nextSols return nextSols } for each levels: solutions = filterSolution(Predicate, solutions, all elems in this level) return solutions 

Answer 3

You can create a separate index that maps the index from one array to the index of another. From the index, you can quickly see if a solution exists or not.

Creating an index will require brute force, but then you only do one. If you want to improve array search, consider using a more appropriate data structure to provide a quick search (for example, red-black trees instead of arrays).

Answer 4

I would save all vectors as heaps , so I can have O(log n) complexity when searching for an element. So, for the whole vector k you get such complexity as O(k * log n)

Answer 5

If predicates keep order in arrays (for example, with your example, if all values ​​are guaranteed non-negative), you can adapt the merge algorithm. Consider the key for each array as the final value (what you get after applying the predicate as many times as necessary for all arrays).

If the predicate does not preserve order (or the arrays are not ordered for starters), you can first sort it by the final value, but the need to do this suggests that a different approach might be better (for example, a hash of the table suggested elsewhere).

Basically, check if the following final value is equal for all arrays. If not, go to the lowest (in only one array) and repeat. If you get all three equal, this is a (possible) solution - go all three before looking for the next one.

A “possible” solution, because you may need to check - if the predicate function can map more than one input value to the same output value, you may have a case where the value is found in some arrays (but not in the first or last) is wrong.

EDIT - there can be big problems when the predicate does not display each input in a unique result - it cannot think at the moment. Basically, a merge approach may work well, but only for certain types of predicate function.