Is there an inversible way to map the permutations of a multiset to integers such that no values are omitted?

In particular I'm interested in mapping a binary number of size n, that consists of exactly two 1s to integers, but out of curiosity I'd like to know if there is a general way to do this.

To illustrate my problem consider the multiset {0,0,1,1}, then a possible mapping would be:

0: {0,0,1,1} 
1: {0,1,0,1}
2: {0,1,1,0}
3: {1,0,0,1}
4: {1,0,1,0}
5: {1,1,0,0}
  • 1
    $\begingroup$ This might be relevant. $\endgroup$ – Jens Oct 27 '17 at 2:38

You want a bijection between the $N = n(n-1)/2$ two element subsets of $\{1, \ldots, n\}$ and the integral range $\{1, \ldots, N\}$;

The clue to finding one is to think about the proof without words that finds the triangular numbers.

Think of the two element subsets as the pairs $(x,y)$ with $x > y$. Then number the corresponding lattice points this way:

            * 11
         *  7 12
      *  4  8 13
   *  2  5  9 14
*  1  3  6 10 15

where the *s are on the diagonal $x=y$.

Then $(x,y)$ is numbered $$ \frac{x(x+1)}{2} -y . $$

The inverse of this bijection is a little harder to calculate.

You could map the string with $1$ in positions $a$ and $b$ (zero based) to $an + b$. That gives you a range for the $n(n-1)/2$ values of $[n+1, \ldots, n^2 -2 ]$ instead of the obvious $[0, \ldots, 2^n -1 ]$ which has many more omitted values.

  • $\begingroup$ Is there a way to do this without gaps? I've edited the question to make my problem more clear. $\endgroup$ – G.G Oct 27 '17 at 0:13
  • $\begingroup$ I'll think about "no gaps" in the morning ... $\endgroup$ – Ethan Bolker Oct 27 '17 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.