7
\$\begingroup\$

Challenge

In this challenge, all numbers are in \$\mathbb{N}_0\$.

Create a function or program that, when given a number \$N\$ and a tuple of \$k\$ numbers \$(n_i)\$ (all ≤ \$N\$), returns the number of ways \$N\$ can be written as a sum of \$k\$ integers (\$x_1 + x_2 + ... + x_k\$) such that \$n_i \le x_i \le N\$.

The input format is not fixed. You can read and parse strings, take two parameters as int and int[], etc.

This is a variation of the classical Integer Partition problem.

Test Cases

\$N=4, n=(0, 0, 2) \implies 6\$ (2+0+2, 1+1+2, 0+2+2, 1+0+3, 0+1+3, 0+0+4)

\$N=121, n=(7, 16, 21, 36, 21, 20) \implies 1\$ (7+16+21+36+21+20)

This is , so the lowest byte count for each language wins!

\$\endgroup\$
6
  • \$\begingroup\$ Do we have to support the edge case where all \$n_i=0\$? \$\endgroup\$
    – Arnauld
    Feb 23 at 12:58
  • \$\begingroup\$ I'm sorry if i dont get the question right, but how are you getting 1+0+3 in the first test case, when 3, or 1 are not in the tuple n? \$\endgroup\$
    – user100752
    Feb 23 at 12:59
  • \$\begingroup\$ @EliteDaMyth the numbers are not required to be in the tuple, but to be elementwise greater than or equal to the numbers in the tuple. Here, (1,0,3) elementwise ≥ (0, 0, 2) \$\endgroup\$
    – zdimension
    Feb 23 at 13:09
  • 2
    \$\begingroup\$ This seems like a well-written challenge, but in future, I'd recommend posting in the Sandbox to get feedback first \$\endgroup\$
    – pxeger
    Feb 23 at 13:18
  • 12
    \$\begingroup\$ Isn't this just the number of ways that \$N - (x_1 + \cdots + x_k)\$ can be written as the sum of \$k\$ non-negative integers? \$\endgroup\$
    – xnor
    Feb 23 at 13:21

11 Answers 11

8
\$\begingroup\$

Jelly, 5 bytes

rŒp§ċ

A dyadic Link accepting the lower bound tuple on the left and the total on the right which yields the count.

Try it online!

How?

rŒp§ċ - Link: T, N       e.g. [2,1,3], 5
r     - inclusive range       [[2,3,4,5],[1,2,3,4,5],[1,2,3,4,5]]
 Œp   - Cartesian product     [[2,1,1],[2,1,2],[2,1,3],[2,1,4],[2,1,5],[2,2,1],...,[5,5,4],[5,5,5]]
   §  - sums                  [ 4,      5,      6,      7,      8,      5,     ..., 14,     15]
    ċ - count (Ns)            2
\$\endgroup\$
7
\$\begingroup\$

Haskell, 35 bytes

n%(x:t)=sum$map(%t)[0..n-x]
n%_=0^n

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Husk, 9 7 bytes

Edit: -2 bytes thanks to user

#¹mΣΠm…

Try it online!

#¹         # number of times that arg 1 appears in the list of
  mΣ       # sums of
    Π      # cartesian product of
     m     # mapping
      …    # range up to arg 1
           # for each element of arg 2
\$\endgroup\$
2
  • \$\begingroup\$ Nice answer! You can save a couple bytes by messing around with superscripts \$\endgroup\$
    – user
    Feb 23 at 20:00
  • \$\begingroup\$ @user - Thanks! I did try to get rid of the superscripts at the end, but never seemed to find the right permutation... \$\endgroup\$ Feb 23 at 20:23
3
\$\begingroup\$

Python 3.8+, 62 bytes

import math
f=lambda S,N:math.comb(S-sum(N)+len(N)-1,len(N)-1)

The result can be found using the formula:

$$R = \binom{N-(\Sigma x_i)+k-1}{k-1}$$

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Shouldn't have trusted the byte counter, I forgot I was on Windows so the CR added 1 byte to the count. \$\endgroup\$
    – zdimension
    Feb 23 at 19:13
  • 2
    \$\begingroup\$ You can make your function anonymous, and also use the new assignment operator to save a few bytes \$\endgroup\$
    – Kirill L.
    Feb 23 at 19:37
2
\$\begingroup\$

Ruby, 62 51 bytes

->n,k{[*1..n-k.sum+z=k.size-1].combination(z).size}

Try it online!

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

JavaScript (ES6), 65 bytes

Expects (n)(list). Uses the formula provided by the OP.

n=>a=>(n-=eval(a.join`-1+`),g=k=>!k||g(--k)*(k-n)/~k)(a.length-1)

Try it online!

How?

The expression eval(a.join('-1+')) subtracts 1 from all entries in a[] except the last one and sums everything. For instance:

[ 2, 3, 4 ] --> "2-1+3-1+4" --> 7

So, this is equivalent to: $$\sum_{i=1}^{k} x_i-k+1$$

We could also use eval(a.join('+~-')) which subtracts 1 from all entries but the first one, leading to the same result.

The helper function g computes the combination.

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

R, 46 bytes

(using n_choose_k)

function(x,y)choose(x-sum(y)+(z=sum(y|1)-1),z)

Try it online!

R, 58 bytes

(by enumeration)

function(x,y)sum(rowSums(z<-expand.grid(Map(`:`,y,x)))==x)

Try it online!

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

Julia 0.6, 38 bytes

port of xnor's answer

n>N=n==[]?0^N:sum([n[2:end]].>0:N-n[])

Try it online!

alternative answer, 38 bytes too

!N=0^N;!(N,x,t...)=sum(.!(0:N-x,t...))

Try it online!

a few more bytes with julia 1.0+

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

Pyth, 14 bytes

.c+-hAQsHJtlHJ

Try it online!

Translation of zdimension's Python 3 answer.

14 bytes

/sMsM*F}RGeAQG

Try it online!

Translation of Jonathan Allan's Jelly answer.

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

JavaScript (ES2020), 59 bytes

f=(n,[h,...t],s=0)=>eval('for(;n>=h;)s+=f(n-h++,t)')??!n&!h

f=(n,[h,...t],s=0)=>eval('for(;n>=h;)s+=f(n-h++,t)')??!n&!h

console.log(f(4, [0,0,2]));
console.log(f(121, [7,16,21,36,21,20]));

Firefox 72+, Chrome 80+, IE no. TIO currently out of date.

Simple brute force, literally.

  • eval() return completion value of given statement(s).
    • Completion value of for statement is completion value of its execute body in last iteration.
    • Completion value of assignment is the value assigned.
    • In case the control flow does not goes into for loop due to the looping condition, for statement has no completion value.
    • As the result, eval(for(;n>=h;)...) returns the value of s (an integer) if once n>=h, and return undefined if n>=h never happened.
  • ?? is nullish coalescing operator which is introduced in ES2020.
    • If left side of ?? is null or undefined, it equals to right side. Otherwise, it returns left side (short circuit evaluation). (Similar as what ?? in C# do.)
    • If n>=h is falsy, it may due to n<h or h is undefined.
    • We found a valid integer partition as long as n == 0 and h is undefined (undefined value of h means the array is empty.).
    • !n&!h check both n and h are falsy. As n may only be integers, it would be 0. h may be integers or undefined. But if h === 0, n >= h is true, the ?? operator short circuit current expression. As the result, we know h is undefined.
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 17 bytes

≔…¹LηζI÷Π⁺ζ⁻θΣηΠζ

Try it online! Link is to verbose version of code. Explanation: Based on the OP's formula.

≔…¹Lηζ

Get the exclusive range from 1 to k.

I÷Π⁺ζ⁻θΣηΠζ

Subtract the sum of xᵢ from N, add it element-wise to the the range, take the product, and divide by the product of the range. This is equivalent to calculating the number of combinations.

\$\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.