10
\$\begingroup\$

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

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Presumably rank and unrank are just names you gave for this challenge; we aren't required to call them that in our code? \$\endgroup\$
    – pxeger
    Nov 12, 2021 at 16:26
  • \$\begingroup\$ @pxeger yes that is right. r and u will do :) \$\endgroup\$
    – user7467
    Nov 12, 2021 at 16:30
  • \$\begingroup\$ 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. \$\endgroup\$
    – alephalpha
    Nov 14, 2021 at 15:03
  • 1
    \$\begingroup\$ @alephalpha Fixed. Yes you can 0-index or 1-index as you choose. \$\endgroup\$
    – user7467
    Nov 14, 2021 at 17:49

3 Answers 3

5
\$\begingroup\$

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:

⊞υE⊕η¬ιF⊖θ⊞υE⊕ηΣ✂…§υι⊕κ±⊕ζ

Explanation:

⊞υE⊕η¬ι

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.

F⊖θ

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

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

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

63 57 bytes for unrank:

⊞υE⊕η¬ιF⊖θ⊞υE⊕ηΣ✂…§υι⊕κ±⊕ζF⮌υ«≔⁰δW¬›§ιηε«≧⁻§ιηε≦⊖η≦⊕δ»⟦Iδ

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

F⮌υ«

Loop over each element.

≔⁰δ

Start with a current element of zero.

W¬›§ιηε«

Repeat while there are still sufficient counts of shorter arrays:

≧⁻§ιηε

Subtract the count from the rank.

≦⊖η

Decrement the remaining sum.

≦⊕δ

Increment the current element.

»⟦Iδ

Output the current element.

53 48 bytes for rank:

⊞υE⊕η¬ιF⊖θ⊞υE⊕ηΣ✂…§υι⊕κ±⊕ζPIΣEε↨¹E駧⮌υκ⁻Σ✂εκθ¹λ

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

PIΣEε↨¹E駧⮌υκ⁻Σ✂εκθ¹λ

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.

≔E⊕η¬ιτFθ«⊞υτ≔⟦⟧σ≔⁰δF⊕η«≧⁺§τκδ⊞σ먪‹κζ≧⁻§τ⁻κζδ»≔στ»F⮌υ«≔⁰δW¬›§ιηε«≧⁻§ιηε≦⊖η≦⊕δ»⟦Iδ

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

≔E⊕η¬ιτFθ«⊞υτ≔⟦⟧σ≔⁰δF⊕η«≧⁺§τκδ⊞σ먪‹κζ≧⁻§τ⁻κζδ»≔στ»PIΣEε↨¹E駧⮌υκ⁻Σ✂εκθ¹λ

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

\$\endgroup\$
12
  • \$\begingroup\$ Thank you for the first (incomprehensible) answer! \$\endgroup\$
    – user7467
    Nov 14, 2021 at 10:14
  • 1
    \$\begingroup\$ @Anush In what way is it incomprehensible? I do try with my explanations... \$\endgroup\$
    – Neil
    Nov 14, 2021 at 15:03
  • 1
    \$\begingroup\$ The explanation was really good. I think it's the characters the language uses which makes it seem incomprehensible \$\endgroup\$
    – Zed
    Nov 14, 2021 at 17:34
  • 1
    \$\begingroup\$ @Neil Yes sorry. Your explanation is fine. I was just commenting on the programming language. It was only a not very funny joke. \$\endgroup\$
    – user7467
    Nov 14, 2021 at 17:51
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Neil
    Nov 14, 2021 at 19:36
4
+50
\$\begingroup\$

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.

\$\endgroup\$
9
  • \$\begingroup\$ I like this answer a lot. You also seem to have the best complexity if I have understood correctly. \$\endgroup\$
    – user7467
    Nov 16, 2021 at 22:18
  • 1
    \$\begingroup\$ P seems to generate l*l*m/2 (or thereabouts) terms, which I can't see you doing in O(lm). \$\endgroup\$
    – Neil
    Nov 16, 2021 at 22:40
  • 1
    \$\begingroup\$ 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). \$\endgroup\$
    – Bubbler
    Nov 16, 2021 at 22:47
  • \$\begingroup\$ Good gracious, I clearly can't count! \$\endgroup\$
    – loopy walt
    Nov 16, 2021 at 22:50
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – loopy walt
    Nov 17, 2021 at 0:36
1
\$\begingroup\$

Pari/GP, 142 bytes

r(l,s,m,a)=y=x^m++\(x-1);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.

\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – Bubbler
    Nov 15, 2021 at 3:40
  • \$\begingroup\$ @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. \$\endgroup\$
    – alephalpha
    Nov 15, 2021 at 4:47
  • 2
    \$\begingroup\$ 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... \$\endgroup\$
    – Bubbler
    Nov 15, 2021 at 5:21
  • \$\begingroup\$ @Bubbler Neil's Charcoal answer is linear in l. Mine is at least l^3, maybe l^4. \$\endgroup\$
    – alephalpha
    Nov 15, 2021 at 5:38
  • \$\begingroup\$ Do you think it’s possible in O(l+m+s) time? \$\endgroup\$
    – user7467
    Nov 15, 2021 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy