18
\$\begingroup\$

In the body of this challenge, \$\begin{pmatrix}n\\k\end{pmatrix}\$ is used to represent the number of combinations of \$k\$ elements of \$n\$, also written as \$\frac{n!}{k!(n-k)!}\$ or \$n\mathrm{C}r\$.

Any nonnegative integer \$m\$, for arbitrary natural (positive) \$r\$, can be written as a unique series of \$r\$ combinations such that $$m=\sum\limits_{i=1}^{r}\begin{pmatrix}C_i\\i\end{pmatrix}$$ provided the sequence \$C\$ both strictly increases (i.e. \$C_{\ell-1}\lneq C_\ell\$) and consists solely of nonnegative integers. \$C\$ is not necessarily unique without these restrictions.


Example

Consider \$m=19\$ and \$r=4\$. Values of \$C_4\$, \$C_3\$, \$C_2\$ and \$C_1\$ must be found for the equation $$19=\sum\limits_{i=1}^4\begin{pmatrix}C_i\\i\end{pmatrix}\\$$ which can be rewritten as $$\begin{pmatrix}C_4\\4\end{pmatrix}+\begin{pmatrix}C_3\\3\end{pmatrix}+\begin{pmatrix}C_2\\2\end{pmatrix}+\begin{pmatrix}C_1\\1\end{pmatrix}=19$$ Begin by finding the largest value of \$C_4\$ which satisfies the inequality \$\begin{pmatrix}C_4\\4\end{pmatrix}\leq 19\$. \$C_4\$ is six: $$\begin{pmatrix}6\\4\end{pmatrix}+\begin{pmatrix}C_3\\3\end{pmatrix}+\begin{pmatrix}C_2\\2\end{pmatrix}+\begin{pmatrix}C_1\\1\end{pmatrix}=19\\15+\begin{pmatrix}C_3\\3\end{pmatrix}+\begin{pmatrix}C_2\\2\end{pmatrix}+\begin{pmatrix}C_1\\1\end{pmatrix}=19\\\begin{pmatrix}C_3\\3\end{pmatrix}+\begin{pmatrix}C_2\\2\end{pmatrix}+\begin{pmatrix}C_1\\1\end{pmatrix}=4$$ The problem has been reduced to \$m=4\$ and \$r=3\$. The largest value of \$C_3\$ which satisfies the inequalities \$\begin{pmatrix}C_3\\3\end{pmatrix}\leq4\$ and \$C_3\lneq C_4\$ must be found. \$C_3\$ is four: $$\begin{pmatrix}4\\3\end{pmatrix}+\begin{pmatrix}C_2\\2\end{pmatrix}+\begin{pmatrix}C_1\\1\end{pmatrix}=4\\4+\begin{pmatrix}C_2\\2\end{pmatrix}+\begin{pmatrix}C_1\\1\end{pmatrix}=4\\\begin{pmatrix}C_2\\2\end{pmatrix}+\begin{pmatrix}C_1\\1\end{pmatrix}=0$$ Any combination of the form \$\begin{pmatrix}n\\k\end{pmatrix}\$ with \$n<k\$ is zero, and so \$C_2=1\$ and \$C_1=0\$: $$\begin{pmatrix}1\\2\end{pmatrix}+\begin{pmatrix}0\\1\end{pmatrix}=0\\0+0=0\\0=0\checkmark$$

Note that \$C_2\$ cannot be zero because then \$C\$ would not strictly increase unless \$C_1\$ were negative, which cannot be the case due to the condition that \$C\$ consists solely of nonnegative integers. The solution is summarized with the statement \$C=(0,1,4,6)\$ (here, 1-based indexing is used). The process followed here is guaranteed to produce the correct \$C\$.


The Challenge

Given \$m\$ and \$r\$, find the elements of \$C\$.

Rules

  • This is so the shortest answer in bytes wins.

  • Assume only valid input will be given.

  • Input and output may assume whatever form is most convenient. This can include outputting the elements of \$C\$ in any order, because \$C\$ strictly increases and so the actual order of the elements is trivially found by sorting them.

  • Terms whose combinations evaluate to zero, e.g. \$C_2\$ and \$C_1\$ in the example, cannot be neglected in output.

  • A program should theoretically work for arbitrarily large values of \$m\$ and \$r\$, but is still acceptable if it is limited by memory constraints.

Test Cases

Here \$m\$ is the first number and \$r\$ is the second, and the output begins with \$C_1\$.

In: 19 4
Out: 0 1 4 6

In: 0 4
Out: 0 1 2 3

In: 40000 6
Out: 6 8 9 11 12 20

In: 6 6
Out: 1 2 3 4 5 6

In: 6 5
Out: 0 1 2 3 6

In: 6 20
Out: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20 (note 14 is skipped)

In: 6 1
Out: 6
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Regarding the one close vote: What needs clarifying? \$\endgroup\$
    – golf69
    Aug 21 '20 at 7:35
  • 3
    \$\begingroup\$ All the mathematical notation looked daunting initially to me, but the explanation seemed pretty clear after reading it. You could possibly add an explanation of 'C choose i' to make it easy for people that aren't immediately fammiliar with the 'bracket' notation for 'choose'. But I'm not the close voter, so this is just my opinion... \$\endgroup\$ Aug 21 '20 at 8:17
  • \$\begingroup\$ Perhaps a link to binomial coefficient \$\endgroup\$ Aug 21 '20 at 8:34
  • \$\begingroup\$ I've fixed that now hopefully \$\endgroup\$
    – golf69
    Aug 21 '20 at 8:38
  • 1
    \$\begingroup\$ I misread that as m=0, my mistake. You are correct that r is only ever positive (edited to note this) @JonathanAllan \$\endgroup\$
    – golf69
    Aug 21 '20 at 17:06
7
\$\begingroup\$

JavaScript (ES6),  95 93 86  82 bytes

Expects (r)(m).

r=>F=(m,x=r)=>r?(g=k=>!k||g(--k)*(k-x)/~k)(r)>m?[...F(m-g(r--,--x)),x]:F(m,x+1):[]

Try it online!

How?

Helper function

The helper function \$g\$ is used to compute:

$$\binom{x}{r}=\frac{x(x-1)\dots(x-r+1)}{r!}=\prod_{k=1}^{r}\frac{x-k+1}{k}$$

(g = k =>     // g is a recursive function taking k
  !k          // if k = 0, stop the recursion and return 1
  ||          // otherwise:
    g(--k)    //   decrement k and do a recursive call with the updated value
    * (k - x) //   multiply the result by k - x
    / ~k      //   divide by -k - 1
              //   which is equivalent to g(k - 1) * (x - k + 1) / k
)(r)          // initial call to g with k = r

Main function

r =>                      // r = requested number of combinations
F = (m, x = r) =>         // F is a recursive function taking the target number m
                          // and a counter x, initialized to r
  r ?                     // if r is not equal to 0:
    g(r) > m ?            //   if C(x, r) is greater than m:
      [ ...F(             //     append the result of a recursive call to F:
          m - g(r--, --x) //       with m - C(x - 1, r) and r - 1
        ),                //     end of recursive call
        x                 //     append x (which was decremented above)
      ]                   //
    :                     //   else:
      F(m, x + 1)         //     increment x until C(x, r) > m
  :                       // else:
    []                    //   stop the recursion
\$\endgroup\$
6
\$\begingroup\$

05AB1E, 13 11 bytes

∞<æIù.ΔācOQ

Inputs in the order \$r,m\$.

Try it online or verify all test cases.

Explanation:

∞           # Push an infinite positive list: [1,2,3,4,5,...]
 <          # Decrease it by 1 to include 0: [0,1,2,3,4,...]
  æ         # Get the powerset of this infinite list
   Iù       # Only leave sublists of a size equal to the first input `r`
     .Δ     # Find the first list which is truthy for:
       ā    #  Push a list in the range [1,length] (without popping the list itself)
        c   #  Get the binomial coefficient of the values at the same indices in the lists
         O  #  Sum those
          Q #  And check if it's equal to the (implicit) second input `m`
            # (after which the found list is output implicitly as result)
\$\endgroup\$
2
  • 2
    \$\begingroup\$ There's something about 05AB1E that always seems to favour the 'brute-force-all-combinations' approach! I read this, liked it, and ported it to R, but it ended-up longer than the 'sensible' approach... \$\endgroup\$ Aug 21 '20 at 9:52
  • 1
    \$\begingroup\$ @DominicvanEssen For me it was the other way around: I started with the sensible approach, but was already at 20 bytes and not completely done yet when I figured a brute-force approach would most likely be much shorter, which indeed is the case. :) And I guess 05AB1E most likely favors that kind of approaches because a lot of its 1-byte builtins (combinations, permutations, cartesian product, etc.) and implicit inputs we can use to our benefit sometimes inside maps/filters/find_firsts. \$\endgroup\$ Aug 21 '20 at 9:58
4
\$\begingroup\$

Jelly, 12 bytes

I feel there may well be shorter, possibly by first creating an outer-product using the binomial function, \$m\$\$r\$.

»Żœc⁸cJ$S⁼ɗƇ

A full-program accepting \$r\$ and \$m\$ which prints the result.
(Or a dyadic Link yielding a list containing the unique result.)

Try it online!

How?

»Żœc⁸cJ$S⁼ɗƇ - Main Link: r, n
»            - maximum (r,n)
 Ż           - zero range -> [0,1,2,...,max(r,n)]
    ⁸        - chain's left argument, r
  œc         - all (r-length) choices (of the zero range)
           Ƈ - filter keep those for which:
          ɗ  -   last three links as a dyad - f(selection, n)
       $     -     last two links as a monad - g(selection)
      J      -       range of length -> [1,2,...,r]
     c       -       binomial (vectorises) [s1C1, s2C2,...,srCr]
        S    -     sum
         ⁼   -     equals (n)?
             - implicit print (a list containing a single element prints that element)
\$\endgroup\$
2
\$\begingroup\$

Python 3.8 (pre-release), 125 121 114 111 108 107 bytes

import math
c=math.comb
f=lambda n,r,k=0:n and(n<c(k+1,r)and f(n-c(k,r),r-1)+[k]or f(n,r,k+1))or[*range(r)]

Try it online!

Explanation: Start from k=0 and keep increasing k as long as comb(k, r) does not exceed n. Update n accordingly. Once the current value of n is 0, simply return the first r integers starting from 0.

\$\endgroup\$
2
\$\begingroup\$

R, 98 96 bytes

s=function(m,r,j=choose(1:(m+r),r))if(r)`if`(!m,1:r-1,c(s(m-max(j[j<=m]),r-1),max(which(j<=m))))

Try it online!

Commented:

choose_series=      
s=function(m,r,         # recursive function s
 j=choose((m+r):1,r))   # j = all relevant values of choose(c,r)
 if(r)                  # if r==0 don't return anything else
  `if`(!m,              # if m==0 ...
   1:r-1,               # ...just return the remaining r-series minus 1
   c(                   # otherswise return ...
    s(                  # recursive call to self, with
     m-                 #   new m = current m minus ...
      max(j[j<=m])      #   ... highest value of j less than or equal to m
     ,r-1),             #   new r = r-1;
    ((m+r):1)[j<=m][1]  # appended to the highest value of c for which...
   )                    # ...j is less than or equal to m
  )

(but, frustratingly, my approach here still comes-out longer than an 84 byte port of Arnauld's approach...)

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 92 bytes

(S=Select)[Subsets[S[0~Range~Max[a=#,b=#2],#~(B=Binomial)~b<a+1&],{b}],Tr@B[#,Range@b]==a&]&

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 39 bytes

NθF⮌ENE⊕ιλ«≔Π⊕ιηW¬›Π⊕ι×θη≦⊕ι≧⁻÷ΠιηθI⟦⊟ι

Try it online! Link is to verbose version of code. Outputs in descending order. Explanation:

Nθ

Input m.

F⮌ENE⊕ιλ«

Loop over the n ranges [0..n-1], [0..n-2], ... [0, 1], [0]. These represent Cᵢ for i from n down to 1 but also the product calculates Cᵢ!/(Cᵢ-i)! for the binomial term.

≔Π⊕ιη

Take the product of the incremented range, which is just i!. This is used to complete the calculation of the binomial term.

W¬›Π⊕ι×θη≦⊕ι

Increment the range, effectively incrementing Cᵢ, until the next binomial term would exceed m. (I don't often get to increment a whole range in Charcoal!)

≧⁻÷Πιηθ

Subtract the current binomial term from m.

I⟦⊟ι

Output Cᵢ (which is always the last element in the range) on its own line.

\$\endgroup\$

Your Answer

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

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