# Finding values in a space that matches a relational query

Assume we have 26 vectors $${A,B,C,....,Z}$$ all have 1 million integers. given a query: $$\vec{query} = (r_a, r_b, r_c, ..., r_c)$$ I want to find a match vector $$\vec{m_{1 \times 26}} = (a, b, c, ..., z)$$ that satisfies the following criterias:

$$a \in A, b \in B, c \in C, ..., z \in Z \\ \text{and} \\ r_{a} = \frac{a}{\sum_{\theta \in m}{\theta}}, r_{b} = \frac{b}{\sum_{\theta \in m}{\theta}}, ..., r_{z} = \frac{z}{\sum_{\theta \in m}{\theta}}$$ in which $$\sum_{\theta \in m}{\theta}$$ is basically sum of the values in vector m. In other words, let say given the amount of share each $$a, b, c, ..., z$$ has in my math vector m, I want to find the elements. Of course, one yet not feasible solution is checking all $${(10^6)^{26}}$$ possible combinations and check if there exists any match. There could be multiple answers, but any of them is fine.

Example: Let say all $${A,B,C,....,Z}$$ are equal to each other and contains elements between $$1$$ and $$10^6$$ like $$\{1,2,3,...,10^6\}$$. given query $$\vec{query} = (\frac{1}{26}, \frac{1}{26}, \frac{1}{26}, ..., \frac{1}{26})$$, $$m$$ is one of the many possible solutions: $$\vec{m} = (1,1,1,...,1).$$

My question is, what could be the fastest algorithm for solving this problem?

• Do you really mean the query and $m$ to be a set, or do you intend them to be an ordered array/vector?
– D.W.
Commented May 6, 2021 at 22:41
• How large are the integers in $A,B,\dots,Z$? Are they always in the range $[0,10^6]$ or so in your application?
– D.W.
Commented May 6, 2021 at 22:41
• @D.W. Thanks for sharing your idea, its really helpful. Not sets, they're both ordered array. So I guess it is a bit misleading. And regarding the numbers, yes in $[1, 10^6]$ but could have repeating values not necessarily unique values Commented May 7, 2021 at 15:57

One approach is to guess $$a$$ (i.e., iterate over all possibilities for it, and the following for each possibility). Then, you can infer the value of $$b$$, namely, $$b = a r_b/r_a$$, so test whether $$b \in B$$. Do the same for each of $$c,\dots,z$$. If they all work, then you have found a solution; otherwise, proceed on to your next guess at $$a$$. This should give you approximately a linear running time if you use the right data structures for storing the vectors (e.g., a hashtable).
A similar approach is to compute the vectors $$A/r_a$$, $$B/r_b$$, ..., $$Z/r_z$$, and then look for an item that occurs in all of those scaled vectors, e.g., using a hashtable or a counter or by sorting and merging the sorted lists.