# rank and unrank arrays of integers

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


# 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).

• Presumably rank and unrank are just names you gave for this challenge; we aren't required to call them that in our code? Nov 12, 2021 at 16:26
• @pxeger yes that is right. r and u will do :)
– user7467
Nov 12, 2021 at 16:30
• Can I use 0-indexing for the rank? It seems that the examples are not consistent: rank((7, 5, 4), (4, 0, 0, 0, 0, 1, 0)) = 451 is 1-indexed, while rank((14, 10, 8), (2, 0, 1, 1, 2, 0, 0, 0, 2, 1, 1, 0, 0, 0)) = 1000000 is 0-indexed. Nov 14, 2021 at 15:03
• @alephalpha Fixed. Yes you can 0-index or 1-index as you choose.
– user7467
Nov 14, 2021 at 17:49

# Charcoal, 116 105 bytes

32 26 bytes of code are shared between the two programs, although I'm currently counting this separately for each program:

⊞υＥ⊕η¬ιＦ⊖θ⊞υＥ⊕ηΣ✂…§υι⊕κ±⊕ζ


Explanation:

⊞υＥ⊕η¬ι


Start with a list of a 1 followed by s 0s. This represents the count of arrays of length 0 with sums of 0 to s.

Ｆ⊖θ


Extend the list of lists up to arrays of length l-1.

⊞υＥ⊕ηΣ✂…§υι⊕κ±⊕ζ


For each sum of 0 to s calculate the number of arrays with that sum.

63 57 bytes for unrank:

⊞υＥ⊕η¬ιＦ⊖θ⊞υＥ⊕ηΣ✂…§υι⊕κ±⊕ζＦ⮌υ«≔⁰δＷ¬›§ιηε«≧⁻§ιηε≦⊖η≦⊕δ»⟦Ｉδ


Try it online! Link is to verbose version of code. Explanation:

Ｆ⮌υ«


Loop over each element.

≔⁰δ


Ｗ¬›§ιηε«


Repeat while there are still sufficient counts of shorter arrays:

≧⁻§ιηε


Subtract the count from the rank.

≦⊖η


Decrement the remaining sum.

≦⊕δ


Increment the current element.

»⟦Ｉδ


Output the current element.

53 48 bytes for rank:

⊞υＥ⊕η¬ιＦ⊖θ⊞υＥ⊕ηΣ✂…§υι⊕κ±⊕ζＰＩΣＥε↨¹Ｅι§§⮌υκ⁻Σ✂εκθ¹λ


Try it online! Link is to verbose version of code. Explanation:

ＰＩΣＥε↨¹Ｅι§§⮌υκ⁻Σ✂εκθ¹λ


For each element in the array to rank, get the count of arrays of the remaining length with sums of between the remaining sum including and excluding the current element.

It's possible to replace the shared code with a 51 byte version that reduces the time complexity by using a sliding window to calculate the counts of arrays with specific lengths and sums.

≔Ｅ⊕η¬ιτＦθ«⊞υτ≔⟦⟧σ≔⁰δＦ⊕η«≧⁺§τκδ⊞σδ¿¬‹κζ≧⁻§τ⁻κζδ»≔στ»Ｆ⮌υ«≔⁰δＷ¬›§ιηε«≧⁻§ιηε≦⊖η≦⊕δ»⟦Ｉδ


Try it online! Link is to verbose version of code.

≔Ｅ⊕η¬ιτＦθ«⊞υτ≔⟦⟧σ≔⁰δＦ⊕η«≧⁺§τκδ⊞σδ¿¬‹κζ≧⁻§τ⁻κζδ»≔στ»ＰＩΣＥε↨¹Ｅι§§⮌υκ⁻Σ✂εκθ¹λ


Try it online! Link is to verbose version of code.

• Thank you for the first (incomprehensible) answer!
– user7467
Nov 14, 2021 at 10:14
• @Anush In what way is it incomprehensible? I do try with my explanations...
– Neil
Nov 14, 2021 at 15:03
• The explanation was really good. I think it's the characters the language uses which makes it seem incomprehensible
– Zed
Nov 14, 2021 at 17:34
• @Neil Yes sorry. Your explanation is fine. I was just commenting on the programming language. It was only a not very funny joke.
– user7467
Nov 14, 2021 at 17:51
• @Anush Actually rank is also l*m*s because it's actually using the sum of the input array which is just s and not l*s. I'm creating an l*m array by summing s other elements each time, so that's the limiting factor of my approach. There may yet be a closed form expression that can calculate the result even more quickly though.
– Neil
Nov 14, 2021 at 19:36

# Python 3, 326,334 bytes (+8 to fix complexity @Bubbler)

def P(l,m,s,o):
*r,o=0,o+m*o[-1:]
for y,z in zip(o[:s+1],-~m*[0]+o):r[len(r):]=r[-1]+y-z,
return l*o and P(l-1,m,s,r[1:])+[o]
def R(p,L):
l,m,s=p;T=P(*p,[1,1]);r=0
for t,l in zip(T,L):r+=t[s]-t[s-l];s-=l
return r
def U(p,r):
l,m,s,*L=p;T=P(*p,[1,0])
for t in T:
j=m
while(t[s]<=r)*j:r-=t[s];s-=1;j-=1
L+=[m-j]
return L


Try it online!

Old version

Doesn't feel very short, but maybe a byte count of "only" 3x the golfy languages is acceptable.

If I'm not mistaken, both R and U are O(lm).**Nonsense!**O(ls) using @Bubbler's suggestion.

The function P creates generalised Pascal's triangles where new rows are generated by taking sums of m+1 elements of the current (m=1 in the original Pascal's triangle). Generalising binomial coefficients which count sums made out a total of of l-s 0s and s 1s, the entries of the generalised triangles count sums of 0s,1s,...,ms with l terms and sum s.

Implementation notes: The output contains a few padding elements on the right end for convenience. By passing [1,0] or [1,1] for o we can choose between the plain triangle (used by U) or the partial row sums (used by R). To limit complexity we calculate only the first s+1 terms in every row.

• I like this answer a lot. You also seem to have the best complexity if I have understood correctly.
– user7467
Nov 16, 2021 at 22:18
• P seems to generate l*l*m/2 (or thereabouts) terms, which I can't see you doing in O(lm).
– Neil
Nov 16, 2021 at 22:40
• And even if you optimize P to generate the smallest necessary region (think of rectangular region in Pascal's triangle), you still need at least O(l*s) terms, not O(l*m). Nov 16, 2021 at 22:47
• Good gracious, I clearly can't count! Nov 16, 2021 at 22:50
• @Neil Since this is a "sliding window" sum we can (and do) take partial sums (s additions per row) and then take differences between pairs of terms m indices apart (or the other way round which is what the code does). So that's O(s) per row. Nov 17, 2021 at 0:36

# Pari/GP, 144 bytes

r(l,s,m,a)=y=1/(1-x)%x^m++;sum(i=1,l,t=a[i];polcoef(y%x^t*y^(l-i),t+s-=t))
u(l,s,m,q)=a=vector(l);for(i=1,l,until(r(l,s,m,a)>q,a[i]++);a[i]--);a


Try it online!

The rank is 0-indexed.

• Can you include the time complexity of r and u? Because as-is u's execution time blows up rather quickly and it isn't 100% clear to all of us that it's still polynomial time. Nov 15, 2021 at 3:40
• @Bubbler I don't know the exact time complexity of r because I don't know what algorithm PARI/GP uses for polynomial multiplication. But even the most naïve algorithm is polynomial time. u's execution time can not blow up because it calls r exactly l+s times. Did you test some invalid rank? In that case it might loop forever. Nov 15, 2021 at 4:47
• I tested with unrank(100,500,20,100000), which doesn't finish in a minute (cf. Charcoal one finishes in a couple seconds). I don't doubt that Pari/GP uses fast enough algorithms for its built-ins, so r and u must have some polynomial time complexity. I guess it's a good example of polynomial time != fast enough... Nov 15, 2021 at 5:21
• @Bubbler Neil's Charcoal answer is linear in l. Mine is at least l^3, maybe l^4. Nov 15, 2021 at 5:38
• Do you think it’s possible in O(l+m+s) time?
– user7467
Nov 15, 2021 at 7:30