Consider all arrays of \$\ell\$ non-negative integers in the range \$0,\dots,m\$. Consider all such arrays whose sum is exactly \$s\$. We can list those in lexicographic order and assign an integer to each one which is simply its rank in the list.
For example, take \$\ell=7, s=5, m=4\$, the list could look like:
(0, 0, 0, 0, 0, 1, 4) rank 1 (0, 0, 0, 0, 0, 2, 3) rank 2 (0, 0, 0, 0, 0, 3, 2) rank 3 (0, 0, 0, 0, 0, 4, 1) rank 4 (0, 0, 0, 0, 1, 0, 4) rank 5 (0, 0, 0, 0, 1, 1, 3) rank 6 (0, 0, 0, 0, 1, 2, 2) rank 7 (0, 0, 0, 0, 1, 3, 1) rank 8 (0, 0, 0, 0, 1, 4, 0) rank 9 [...] (3, 2, 0, 0, 0, 0, 0) rank 449 (4, 0, 0, 0, 0, 0, 1) rank 450 (4, 0, 0, 0, 0, 1, 0) rank 451 (4, 0, 0, 0, 1, 0, 0) rank 452 (4, 0, 0, 1, 0, 0, 0) rank 453 (4, 0, 1, 0, 0, 0, 0) rank 454 (4, 1, 0, 0, 0, 0, 0) rank 455 This challenge requires you to produce two pieces of code/functions.
- Given a rank, compute the corresponding array directly. Call this function
unrank() - Given an array, compute its rank. Call this function
rank()
Your code should run in polynomial time. That is it shouldn't be brute force and more specifically it should take \$O(\ell^a s^b m^c)\$ time for fixed non-negative integers \$a, b, c\$. Any non-brute force method is likely to satisfy this requirement.
Examples
unrank((7, 5, 4), 9) = (0, 0, 0, 0, 1, 4, 0) rank((7, 5, 4), (4, 0, 0, 0, 0, 1, 0)) = 451 unrank((14,10, 8), 100001) = (0, 0, 0, 1, 0, 0, 1, 3, 1, 2, 0, 0, 2, 0) rank((14, 10, 8), (2, 0, 1, 1, 2, 0, 0, 0, 2, 1, 1, 0, 0, 0)) = 1000001 Your score will be the total size for your code
Bounty notes
The bounty will be awarded to the answer with the best time complexity. Current best is \$O(\ell s)\$ time first by @loopywait (with help from Bubbler).
rankandunrankare just names you gave for this challenge; we aren't required to call them that in our code? \$\endgroup\$randuwill do :) \$\endgroup\$rank((7, 5, 4), (4, 0, 0, 0, 0, 1, 0)) = 451is 1-indexed, whilerank((14, 10, 8), (2, 0, 1, 1, 2, 0, 0, 0, 2, 1, 1, 0, 0, 0)) = 1000000is 0-indexed. \$\endgroup\$