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
    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.2012-03-19
  • 0
    Is the question more clear now?2012-03-19
  • 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