What elegant solution exists for this pattern? Multi-Level Searching

Question

Hi,

Assume that we have multiple 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 proceed to the next array with the same predicate. For example, we have v1, v2, v3 as the arrays:

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

I could say that the predicate is: next_element == previous_element^2
A valid sequence from the above example is: 2 -> 4 -> 16
Actually, in this example there isn't another valid sequence. I could write three loops to brute-force the mentioned example, but what if the number of arrays is variable, but with know order of course, how would you solve this problem?

Hints, or references to design patters are very appreciated. I shall do it in C++, but I just need the idea.

Thanks,

Answer 1

If you order your arrays beforehand, the search can be done much faster. You could start on your smaller array, then binary-search for expected numbers on each of them. This would be O(n*k*logM), n being the size of the smallest array, k being the numbers of arrays, M being the size of larger array

This could be done even faster if you use Hashmaps instead of arrays. This would let you search in O(n*k).

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

For simplicity, I'll start from 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 booleans in there to know if the sequence exist or not

Answer 2

You could generate a seperate index that map an index from one array to the index of another. From the index you can quickly see if an solution exists or not.

Generating the index would require a brute force approach but then you'd do it only one. If you want to improve the array search, consider using a more appropriate data structure to allow for fast search (red-black trees for example instead of arrays).

Answer 3

I would keep all vectors as heaps so I can have O(log n) complexity when searching for an element. So for a total of k vectors you will get a complexity like O(k * log n)

Answer 4

(Design patterns apply to class and API design to improve code quality, but they aren't for solving computational problems.)

Depending on the cases:

1. If the arrays comes in random order, and you have finite space requirement, then brute-force is the only solution. O(N^k) time (k = 3), O(1) space.
2. If the predicate is not invertible (e.g. SHA1(next_elem) xor SHA1(prev_elem) == 0x1234), then brute force is also the only solution.
3. If you can expense space, then create hash sets for v2 and v3, so you can quickly find the next element that satisfies the predicate. O(N + b^k) time, O(kN) space. (b = max number of next_elem that satisfy the predicate given a prev_elem)
4. If the arrays are sorted and bounded, you can also use binary search instead of the hash table to avoid using space. O(N (log N)^k-1 + b^k) time, O(1) space.

(All of the space count doesn't take account to stack usage due to recursion.)

A general way that consumes up to O(Nb^k) space is to build the solution by successively filtering, e.g.

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 5

If the predicates preserve the ordering in the arrays (e.g. with your example, if the values are all guaranteed non-negative), you could adapt a merge algorithm. Consider the key for each array to be the end-value (what you get after applying the predicate as many times as needed for all arrays).

If the predicate doesn't preserve ordering (or the arrays aren't ordered to start) you can sort by the end-value first, but the need to do that suggests that another approach may be better (such as the hash tables suggested elsewhere).

Basically, check whether the next end-value is equal for all arrays. If not, step over the lowest (in one array only) and repeat. If you get all three equal, that is a (possible) solution - step over all three before searching for the next.

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

EDIT - there may be bigger problems when the predicate doesn't map each input to a unique output - can't think at the moment. Basically, the merge approach can work well, but only for certain kinds of predicate function.