2

I'm trying to find a bijective mapping between a permutation and an index. The permutation refers to a 4-tuple of integers.

Tuples consist of $(a,b,c,d)$ such that $a,b,c,d \in [1;15]$ with $a \leq b \leq c \leq d$. For instance, these are possible:

  • 0,0,0,0
  • 0,2,7,8
  • 8,9,15,15

And these, for instance, are not possible:

  • 1,0,0,0
  • 0,1,2,1

I would like to map these tuples to an index and back. As an example:

  • 0,0,0,0 $\leftrightarrow 0$
  • 0,0,0,1 $\leftrightarrow 1$
  • ...
  • 0,0,0,15 $\leftrightarrow 15$
  • 0,0,1,0 $\leftrightarrow 16$
  • ...
  • 6,15,15,15 $\leftrightarrow k$
  • 7,7,7,7 $\leftrightarrow k+1$
  • ...
  • 15,15,15,15 $\leftrightarrow 3876$ (19 choose 4)

The order given above is not the only one, I am perfectly fine with any bijective mapping as long as it is not too computationally expensive. Can you help me find a formula?

Some background: I'm using this idea to compress sorted lists of integers. Right now I use a loopup table for translation, but it is rather large, so I am hoping to find a way with only rather elementary calculations. (But just out of curiousity, I would also love to see how this can be generalized to different numbers of elements and larger value ranges.)

The number 3876 (total number of valid combinations) is from this question, I also confirmed it experimentally.

mafu
  • 537

1 Answers1

1

$$f(a,b,c,d)=\binom{d+3}{4}+\binom{c+2}{3}+\binom{b+1}{2}+a$$ Or, if your binomial function doesn't like $\binom{3}{4}=0$, use this: $$f(a,b,c,d)=\frac{d}{4}\binom{d+3}{3}+\frac{c}{3}\binom{c+2}{2}+\frac{b(b+1)}{2}+a$$ Either way, the values are mapped like this:

  • 0,0,0,0 $\leftrightarrow 0$

  • 0,0,0,1 $\leftrightarrow 1$

  • 0,0,1,1 $\leftrightarrow 2$

  • 0,1,1,1 $\leftrightarrow 3$

  • 1,1,1,1 $\leftrightarrow 4$

  • 0,0,0,2 $\leftrightarrow 5$

  • 0,0,1,2 $\leftrightarrow 6$

  • ...

  • 2,2,2,2 $\leftrightarrow 14$

  • 0,0,0,3 $\leftrightarrow 15$

  • ...

  • 14,15,15,15 $\leftrightarrow 3874$

  • 15,15,15,15 $\leftrightarrow 3875$ (This is $\binom{19}{4}-1$ because the first index is $0$)

Notice that this mapping is expandable. You can increase the max value without affecting the mapping of lesser values: 0,0,0,16 $\leftrightarrow 3976$

The reverse, finding a tuple given its index, involves quartic and cubic equations and is probably easiest with look-up tables. The tables are small, just $16$ elements for each of $b,c,d$, and can also be used in place of the above function as they contain the pre-calculated values of the binomials.

$L_d(0\text{ to }15)$ holds the values $L_d(d)=\binom{d+3}{4}$

$L_c(0\text{ to }15)$ holds the values $L_c(c)=\binom{c+2}{3}$

$L_b(0\text{ to }15)$ holds the values $L_b(b)=\binom{b+1}{2}$

Given index $x$, find the greatest value $d$ for which $L_d(d)\le x$

Then let $x=x-L_d(d)$ and find the greatest value $c$ for which $L_c(c)\le x$

Then let $x=x-L_c(c)$ and find the greatest value $b$ for which $L_b(b)\le x$

Finally, let $a=x-L_b(b)$

Using the tables to find the index:$$f(a,b,c,d)=L_d(d)+L_c(c)+L_b(b)+a$$

Daniel Mathias
  • 5,415
  • 1
  • 12
  • 21
  • Excellent and very helpful answer. I tested and confirmed it works fine. Can you briefly explain how you arrived at the first line? – mafu Dec 27 '18 at 20:35
  • 1
    @mafu Years ago, I needed to map number pairs $(a,b)$ to unique indices. As I wrote the list in this particular order, I noticed the relation of $b$ to the triangular numbers. This yielded $f(a,b)=\binom{b+1}{2}+a$. Some time later, I attempted to modify the formula to work for $3$ variables and found that $f(a,b,c)=\binom{c+2}{3}+f(a,b)$, and this pattern continues for any number of variables. $f(a,b,c,d,e)=\binom{e+4}{5}+f(a,b,c,d)$ and so on – Daniel Mathias Dec 27 '18 at 20:58