Constrained integer partition

Question

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 code-golf, so the lowest byte count for each language wins!

• Arnauld: Do we have to support the edge case where all \$n_i=0\$?
• user100752: 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?
• zdimension: @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)
• pxeger: This seems like a well-written challenge, but in future, I'd recommend posting in the Sandbox to get feedback first
• xnor: 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?

Answer 1

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

Answer 2

Haskell, 35 bytes

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

Try it online!

Answer 3

Husk, (削除) 9 (削除ここまで) 7 bytes

Edit: -2 bytes thanks to user

#1mΣΠm...

Try it online!

#1 # 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

• user: Nice answer! You can save a couple bytes by messing around with superscripts
• Dominic van Essen: @user - Thanks! I did try to get rid of the superscripts at the end, but never seemed to find the right permutation...

Answer 4

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}$$

• zdimension: Shouldn't have trusted the byte counter, I forgot I was on Windows so the CR added 1 byte to the count.
• Kirill L.: You can make your function anonymous, and also use the new assignment operator to save a few bytes

Answer 5

Ruby, (削除) 62 (削除ここまで) 51 bytes

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

Try it online!

Answer 6

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.

Answer 7

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!

Answer 8

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+

Answer 9

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.

Answer 10

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.

Answer 11

Charcoal, 17 bytes

≔...1LηζI÷Π+ζ−θΣηΠζ

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

≔...1Lηζ

Get the exclusive range from 1 to k.

I÷Π+ζ−θΣηΠζ

Subtract the sum of xi 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.