Unique representation of 5-number sets with values 1-13

Question

From a simulation I get 5 numbers 1-13. The nature of the simulation is that I do not get the numbers ordered. The value/rank of the the tuple is not order dependent 5 5 5 2 2 = 2 5 2 5 5. Values can repeat but they can repeat at most 4 times (it is a deck of cards). As it turn out there are 6175 combinations. Calculate the value of the tuple is expensive but it is pretty cheap to just generate the tuples in value order - save that and do a dictionary lookup. Without sorting the numbers what is the smallest number to uniquely represent the 5 number combination and how to generate that number?

Right now I just raise 5 to the 0-12 power and add the 5 as a proof of concept and it works. But that is fairly expensive and uses 32 bits. I want to get the bits and compute down. How might I do that?

Yes I have had few questions on this subject but I promise to make this my last.

In a related question got an answer for 5 numbers 1-52 in 27 bits using some magic numbers and XOR. I cannot figure out how to create those magic numbers for 1-13.

Answer 1

Here is a solution with 20 bits. Consider the following array:

0x000f2616, 0x000dbcce, 0x000533cf, 0x0007d943, 0x000a180c,
0x000f69f2, 0x0005e214, 0x0009da04, 0x000e101a, 0x000c495c,
0x0009cfaa, 0x000ff60d, 0x0000103d

Each of these numbers $x_1,\ldots,x_{13}$ is 20 bits long. Given a hand $a,b,c,d,e$, compute the 20 least significant bits of $x_a+x_b+x_c+x_d+x_e$. You can easily check that this results in a value that identifies a hand uniquely.

I found these values by randomly generating arrays until one of them worked, so it's possible that a better construction exists (such as one using codes over $\mathbb{F}_5$).

---

Here is another solution, which results in keys in the range [0,441100]. Let $p = 441101 \approx 2^{18.75}$, which is prime. The key corresponding to a hand $a,b,c,d,e$ is $5^a+5^b+5^c+5^d+5^e \bmod{p}$. This is the minimal prime that works. I calculated it by factoring all differences of $5^a+5^b+5^c+5^d+5^e$ for all pairs of hands.

You can also implement this using the array

1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 188721, 61403, 307015, 211772

Add the corresponding numbers, and (optionally) reduce modulo 441101.

Answer 2

Sorting five numbers is so fast that I don't see why you won't do it (implicitly or explicitly). For instance, you can just use insertion sort while creating the tuples. Or use counting sort, or radix sort (since you know the range of values and it's small).

Once the tuples are sorted, you can just number them by the lexicographic order, which is a nice exercise to do.

Note that whatever you do, you'll need at least $\log_2\bigl(\binom{17}{5} - 13\bigr) \approx 13$ bits, which means in most real settings that you'll just use which ever Int datatype is available (maybe downgrading to Int16 or UInt16 if you manage to get that low, and such types are available).

Be mindful of premature optimization. First, do something. Then investigate if what you've got is fast enough. If not, find out where the bottleneck is. My gut says is probably not here.

---

I think sorting is a lower bound on this problem. If you have a unique numbering of tuples, looking up the sorted version in a table is an $O(1)$ operation, so in terms of complexity theory, computing this number can't be $\Theta$-faster than sorting (extending to arbitrarily large tuples). That does not say much about practical implementations (of constant-sized tuples), but it should give you some ideas about where natural boundaries may be.

---

For the fun of it, here is an idea to compute unique numbers without sorting. Assign each possible value $i$ the $i$-th prime $p_i$. If $i$ appears $c_i$ times in the tuples, its number is

$\qquad\displaystyle \prod_{i=1}^{13} p_i^{c_i}$,

which is unique because prime factorizations uniquely map to numbers. You can compute this while iterating through the tuple once:

numberOf(t: (Int, Int, Int, Int, Int)) -> Int {
  c  = [Int](13)
  nr = 1

  for i = 1 .. 5 {
    c[t.i] += 1
    nr *= p[t.i]
  }

  return nr
}

The largest number you can get is the one of $(13, 13, 13, 13, 12)$ which turns out to have 70 bits -- not practical at all!