Mapping permutations of multisets to integers

Question

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}

Answer 1

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.