[Python] Number of integer sequences of length n for which the sum is m

Overview

Challenge from Dwango Qualifying C --Kill / Death To solve, the sum is a certain value (positive) We needed the number of integer sequences and the number of unique combinations of them. Both can be enumerated on a two-dimensional array with $ O (nm) $ when the length of the integer sequence is $ n $ and the sum is $ m $.

Find the number of integer sequences

As an examplem=4, n=3When,● ● ● ●Can be considered to divide into three compartments, for example● ● | ● | ●It can be expressed as. This is a question of where to put $ n-1 $ | in $ m + n-1 $, and the number of combinations is $ _ {n-1 + m} C _ {n- It is calculated by 1} $, and in this example, there are $ _6 C _2 = 15 $.

Enumerating integer sequences
4 0 0
3 0 1
3 1 0
2 0 2
2 1 1
2 2 0
1 0 3
1 1 2
1 2 1
1 3 0
0 0 4
0 1 3
0 2 2
0 3 1
0 4 0
Of these integer sequences, for example, `400`,` 0 4 0 `, and` 0 0 4` consist of the same combination in a different order.

Enumerate the number of integer sequences

Since it takes time to calculate $ _n C _r $ depending on how the value is taken, there are cases where it can be speeded up by enumerating the number of integer sequences. Here, the following recurrence formula is used. $ P (n, m) $ is the number of integer sequences of length $ n $ and sum $ m $.

P(n,m)= 
\begin{cases}
1 & (n,m=0)\\

P(n-1,m) & (m=0, 1 \leq n) \\
P(n-1,m)+P(n,m-1) & (1 \leq m, 1 \leq n) \\
0 & (otherwise) 
\end{cases}

The number of integer sequences up to the $ i $ th element whose sum is exactly $ j $ is the number of integer sequences whose sum is exactly $ j $ at the $ i-1 $ th element (that is, the $ i $ th element is (When $ 0 $) and the number of integer sequences whose sum is exactly $ j-1 $ up to the $ i $ th element. It can be implemented as follows.

P = []
cur = [0]*(m+1)
cur[0] = 1
for i in range(1, n+1):
    for j in range(1, m+1):
        cur[j] += cur[j-1]
    P.append(cur.copy())

Intuitive understanding of recurrence formulas

When enumerating an integer sequence of $ P (2,4) $

4 0 0
#Up to here is P(1,4)

0 4 0
3 1 0
2 2 0
1 3 0
#Up to here is P(2,4)

Now, if you subtract $ 1 $ from all the second elements of a sequence of integers whose length can be represented by exactly $ 2 $

0 3
3 0
2 1
1 2

And we get an integer sequence of $ P (2,3) $. Conversely, if you add $ 1 $ to all the second elements of $ P (2,3) $, the second element is greater than or equal to $ 0 $, so the sum that can be represented by exactly $ 2 $ in length is $ 4 $. You get a sequence of integers.

List the number of combinations

Find the number of unique combinations of the integer sequences listed earlier, excluding the same combinations in different orders. $ C (n, m) $ is a combination of $ n $ integers that sums $ m $, and is calculated by the following recurrence formula.

C(n,m)= 
\begin{cases}
1 & (n,m=0)\\

C(n-1,m) & (m < n, 1 \leq n) \\
C(n-1,m)+C(n,m-n) & (n \leq m, 1 \leq n) \\
0 & (otherwise) 
\end{cases}

The number of integer sequences up to the $ i $ th element whose sum is exactly $ j $ is the number of integer sequences whose sum is exactly $ j $ at the $ i-1 $ th element (that is, the $ i $ th element is (When $ 0 $) and the number of integer sequences whose sum is exactly $ ji $ up to the $ i $ th element. It can be implemented as follows.

C = []
cur = [0]*(m+1)
cur[0] = 1
for i in range(1, n+1):
    for j in range(i, m+1):
        cur[j] += cur[j-i]
    C.append(cur.copy())

Intuitive understanding of recurrence formulas

If you enumerate $ C (3,4) $,

4 0 0
#Up to here is C(1,4)

2 2 0
3 1 0
#Up to here is C(2,4)

2 1 1
#Up to here is C(3,4)

Will be. By the way, if the combination of integers whose length is exactly $ 2 $ and the sum is $ 4 $ is represented by *


2 * *
2 * *
0

3 * * *
1 *
0

If you transpose this and read it

2 2
* *
* *

2 1 1
* * *
*

And a combination of integers with a length of just $ 2 $ and a sum of $ 4 $ can be read as a combination of integers of any length with a maximum value of $ 2 $ and a sum of $ 4 $. Here, it can be seen that the integer combination after transposition always starts with $ 2 $, and thereafter it can be represented by the integer combination of $ C (2,4-2) = C (2,2) $.

reference

Math Girl ★ Play with the recurrence formula of partition number --incognita et cognita

Recommended Posts

[Python] Number of integer sequences of length n for which the sum is m
What is the python underscore (_) for?
Change the length of Python csv strings
[Example of Python improvement] What is the recommended learning site for Python beginners?
Is the number equivalent to an integer?
[python] [meta] Is the type of python a type?
Pandas of the beginner, by the beginner, for the beginner [Python]
Align the number of samples between classes of data for machine learning with Python
Output the number of CPU cores in Python
The story of low learning costs for Python
The answer of "1/2" is different between python2 and 3
Wagtail is the best CMS for Python! (Perhaps)
Calculate the total number of combinations with python
Image processing? The story of starting Python for
This is the only basic review of Python ~ 1 ~
This is the only basic review of Python ~ 2 ~
Code for checking the operation of Python Matplotlib
Find the geometric mean of n! Using Python
This is the only basic review of Python ~ 3 ~
A python script that gets the number of jobs for a specified condition from indeed.com
Check the processing time and the number of calls for each process in python (cProfile)
Check if the string is a number in python
python beginners tried to predict the number of criminals
[Python] A program that counts the number of valleys
How to get the number of digits in Python
Summarized the types of sum of squares for analysis of variance
Get the size (number of elements) of UnionFind in Python
Electron is the best solution for Python multi-platform development
Find the maximum value, minimum value, and number of elements when the integer N is on the first line of the standard input and N integers follow.
Why is the first argument of [Python] Class self?
[Python] Get the number of views of all posted articles
the zen of Python
[Environment construction] Procedure for implementing the Python environment of Rabbit Challenge, which is a JDLA certified E qualification measure account, with Databricks
Get the number of specific elements in a python list
Python --Find out number of groups in the regex expression
[Python] Which is executed first, the class variable or __init__?
Consideration for Python decorators of the type that passes variables
[Homology] Count the number of holes in data with Python
Scrapy-Redis is recommended for crawling a large number of domains
Get the number of occurrences for each element in the list
Which method is best for asynchronous processing of TCP server?
What is the default TLS version of the python requests module?
The image display function of iTerm is convenient for image processing.
[Python] The biggest weakness / disadvantage of Google Colaboratory [For beginners]
Google search for the last line of the file in Python
Initial setting of Mac ~ Python (pyenv) installation is the fastest
Aggregate the number of hits per second for one day from the web server log with Python