1
$\begingroup$

I have a very big set of non-empty arrays of possibly repeated numbers sorted in a weakly-decreasing order where each number belongs to the interval $[1, 55]$ and the sum of the elements of each array is always $\leq 55$. For example, the array $A=[5, 5, 3, 3, 3, 3, 1, 1, 1]$ contains 9 elements and its sum is $25$.

I want to codify each possible array on a bitstring that is as short as possible (this codification would be used as a key of a hash-table to know which arrays do or do not occur in my collection).

The most-space efficient way to codify the arrays that I have been able to find requires 109 bits: given an array $A$, each number $x$ from $A$ is codified by storing $x$ consecutive $1$s followed by a $0$ to separate the number from the following one. Consider the array $A$ presented above. I would codify it as (five $1$s, then a $0$, then five $1$s, then a $0$, the three $1$s, then a $0$, etc): $$ 111110111110111011101110111010101 $$

The worst case would be an array containing fifty five $1$s, which would be codified as fifty five $1$s separeted by fifty four $0$s: 109 bits. The number of $1$s on the bitstring equals the sum of the array, and the number of $0$s is the size of the array minus 1.

But, is there way to use it even less bits to codify any possible array? I would like to use 64-bits at most.

Optimal approach (I guess):

If I consider all the possible arrays that sum $n$ as all the possible partitions of $n$, the total number of arrays I could have in total is $$P(n) = \sum_{n = 1}^{55}p(n)$$ where $p(n)$ is the partition function. I have compute this sum and there's in total $2984864$ possible partitions of all numbers $n\in[1, 55]$. If given an array $A$ I'm able to compute an unique index $I_A\in[1, 2984864]$ for it (so that any other array $B=A$ computes the same index), I would only need 22 bits to codify each array, because $\log_2(2984864)=21.509\ldots$

Is there any computationally tractable algorithm to compute such an index?

$\endgroup$

1 Answer 1

2
$\begingroup$

Your question concerns ranking and unranking of integer partitions. Ranking is the process of converting an integer partition into an index, and unranking is the opposite operation.

Let us first consider ranking and unranking of partitions of exactly $n$ with $k$ parts, which are counted by $p(n,k)$. Enumerating over the minimal element $m$ and the number of times $\ell$ it appears, when $k > 0$ we have $$ p(n,k) = \sum_{m=1}^{\lfloor n/k \rfloor} \sum_{\ell=1}^k p(n-km,k-\ell). $$ The base cases are $p(0,0) = 1$ and $p(n,0) = 0$ if $n > 0$.

We can partition accordingly the interval $[p(n,k)]$ into intervals of length $p(n-km,k-\ell)$ in some arbitrary way. The interval corresponding to some $(m,k)$ will be used to index partitions of the corresponding type. This leads to recursive ranking and unranking algorithms which I will let you work out. These algorithms require knowledge of $p(n,k)$, which can be computed using dynamic programming through the recursion above.

Using $p(n) = \sum_{k=1}^n p(n,k)$, we can similarly rank and unrank partitions of $n$ with an arbitrary number of parts. Using $P(n) = \sum_{r=0}^n p(r)$, we can similarly rank and unrank partitions of at most $n$.

$\endgroup$
1
  • $\begingroup$ I haven't really understand yet why the intervals are of length $p(n-km, k-l)$. Why substracting, in particular, $km$ and $l$ and not different amounts? $\endgroup$
    – ABu
    Nov 22, 2022 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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