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.

$\endgroup$
3
  • $\begingroup$ I don't understand the question. What does "pick $\sqrt n$" mean? What are "the configurations"? What is $f$, and what are its arguments? You're assuming a lot of telepathic ability. $\endgroup$
    – joriki
    Mar 19, 2012 at 18:59
  • $\begingroup$ Is the question more clear now? $\endgroup$ Mar 19, 2012 at 20:41
  • $\begingroup$ 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 :-) $\endgroup$ Apr 4, 2012 at 9:20

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .