1
$\begingroup$

If you have a set of $n$ integers ranging from $1$ to $n$ and you need to pick (create a tuple with length) $\sqrt{n}$ ($n$ is a valid square). One could encode that with an integer ranging from $1$ to $n!/(n-\sqrt{n})!$ in such a way that the configurations (a sequence of $\sqrt{n}$ integers ranging from $1$ to $n$ with no duplicates) are ordered (and so can be calculated backwards). Therefore a function $f$ can be defined that calculates the rank of a configuration. For instance with $n=4$: $f\left(\left[1,2\right]\right)=1$, $f\left(\left[1,3\right]\right)=2$, $f\left(\left[1,4\right]\right)=3$ , $f\left(\left[2,1\right]\right)=4$,....

I was wondering if there is such an encoding so it's easy to determine when two configurations have an integer in common.

  • 0
    If I understood it correctly, your "default" $f$ is the lexicographic ordinal of the vector. Extracting the components of the vector from that ordinal number is relatively straight forward (but does require maintaining a list or some such). Is the complexity of that task too high for your purposes? Just trying to find a benchmark here :-)2012-04-04

1 Answers 1

1

Is it considered that $[1,2]$ and $[2,1]$ have an integer in common? If so, then you can let $f(a,b,c,\dots)=p_ap_b^2p_c^3\dots$, where $p_n$ is the $n$th prime. Configurations $C_1$ and $C_2$ will have an integer in common if and only if the greatest common divisor of $f(C_1)$ and $f(C_2)$ exceeds 1.