Hướng dẫn integer partition python - python phân vùng số nguyên

Tôi cần phải giải quyết một vấn đề tương tự, cụ thể là phân vùng của số nguyên

[
    [5, 0, 0], [4, 1, 0], [3, 2, 0], [2, 3, 0], [1, 4, 0],
    [0, 5, 0], [4, 0, 1], [3, 1, 1], [2, 2, 1], [1, 3, 1],
    [0, 4, 1], [3, 0, 2], [2, 1, 2], [1, 2, 2], [0, 3, 2],
    [2, 0, 3], [1, 1, 3], [0, 2, 3], [1, 0, 4], [0, 1, 4],
    [0, 0, 5]
]

[
    [5, 0, 0], [4, 1, 0], [3, 2, 0], [2, 3, 0], [1, 4, 0],
    [0, 5, 0], [4, 0, 1], [3, 1, 1], [2, 2, 1], [1, 3, 1],
    [0, 4, 1], [3, 0, 2], [2, 1, 2], [1, 2, 2], [0, 3, 2],
    [2, 0, 3], [1, 1, 3], [0, 2, 3], [1, 0, 4], [0, 1, 4],
    [0, 0, 5]
]

def partition(n, d, depth=0):
    if d == depth:
        return [[]]
    return [
        item + [i]
        for i in range(n+1)
        for item in partition(n-i, d, depth=depth+1)
        ]


# extend with n-sum(entries)
n = 5
d = 3
lst = [[n-sum(p)] + p for p in partition(n, d-1)]

print(lst)

Output:

[
    [5, 0, 0], [4, 1, 0], [3, 2, 0], [2, 3, 0], [1, 4, 0],
    [0, 5, 0], [4, 0, 1], [3, 1, 1], [2, 2, 1], [1, 3, 1],
    [0, 4, 1], [3, 0, 2], [2, 1, 2], [1, 2, 2], [0, 3, 2],
    [2, 0, 3], [1, 1, 3], [0, 2, 3], [1, 0, 4], [0, 1, 4],
    [0, 0, 5]
]

Tác giả: Kazi Abu Rousan: Kazi Abu Rousan

Nhà toán học thuần túy, giống như nhạc sĩ, là người tạo ra thế giới đẹp của mình.

Bertrand Russell

Hôm nay chúng ta sẽ thảo luận về một trong những ý tưởng hấp dẫn nhất về lý thuyết số, rất đơn giản để hiểu nhưng rất phức tạp để tham gia. Hôm nay chúng ta sẽ thấy cách tìm số phân vùng của bất kỳ số nguyên dương $ n $.Partition Number of any positive integer $n$.

Giống như mọi blog, trọng tâm chính của chúng tôi sẽ là viết một chương trình để tìm phân vùng bằng Python. Nhưng hôm nay chúng tôi sẽ sử dụng một điều rất đặc biệt, chúng tôi sẽ sử dụng Thanh tra toán học - một môi trường lập trình trực quan. Nó sử dụng mã python bình thường, nhưng nó có thể hiển thị cho bạn trực quan (biểu diễn khối) của mã bằng cách sử dụng một thứ gọi là trình soạn thảo nút. Đây là một video để hiển thị tính năng của nó.Math Inspector - A visual programming environment. It uses normal python code, but it can show you visual (block representation) of the code using something called Node Editor. Here is a video to show it's feature.

Đẹp phải không? Hãy bắt đầu cuộc thảo luận của chúng tôi.

Số phân vùng là gì?

Trong lý thuyết số, một phân vùng của số nguyên dương $ n $, còn được gọi là phân vùng số nguyên, là một cách viết $ n $ như một tổng số nguyên dương (hai tổng chỉ khác nhau theo thứ tự của bản tóm tắt của chúng được coi là giống nhau Phân vùng, tức là, $ 2+ 4 = 4+ 2 $). Số phân vùng của $ n $ được viết là $ p (n) $Partition of a positive integer $n$, also called an Integer Partition, is a way of writing $n$ as a sum of positive integers (two sums that differ only in the order of their summands are considered the same partition, i.e., $2+4 = 4+ 2$). The partition number of $n$ is written as $p(n)$

Ví dụ, hãy lấy số $ 5 $. Đó là phân vùng là;

$$ 5 = 5 +0 \ \ \ \ \\ = 4 + 1 \ \ \ \ \\ = 3 + 2 \ \ \ \ \ \ = 3 + 1+ 1 \ \ \ \ \\ = 2+1+1+1 \ \\ = 1+1+1+1+1 $$

Do đó, $ P (5) = 7 $. Dễ dàng phải không ?, Hãy xem phân vùng của tất cả các số từ $ 0 $ đến $ 6 $.

Lưu ý: Số phân vùng là $ 0 $ được lấy là $ 1 $.: The partition number of $0$ is taken as $1$.

Xem mức độ dễ dàng của nó không hiểu ý nghĩa của điều này và bạn có thể dễ dàng tìm thấy các phân vùng của các số nhỏ bằng tay. Nhưng những gì về số lượng lớn ?, Giống như $ P (200) $?

Tìm số phân vùng

Không có công thức đơn giản cho số phân vùng. Chúng tôi thường sử dụng đệ quy nhưng nếu bạn chỉ muốn một công thức tạo ra số phân vùng của bất kỳ số nguyên $ n $, thì bạn phải sử dụng công thức kinh hoàng này:Partition Number. We normally use recursion but if you want just a formula which generate partition number of any integer $n$, then you have to use this horrifying formula:

Chỉ cần nhìn vào điều này có thể cho bạn cơn ác mộng. Vì vậy, có bất kỳ phương pháp nào khác không ?, Vâng.

Mặc dù, không có bất kỳ biểu thức hình thức đóng nào cho chức năng phân vùng cho đến bây giờ, nhưng nó có cả hai mở rộng tiệm cận (công việc của Ramanujan) gần đúng với các mối quan hệ nó và tái phát (công việc của Euler) mà nó có thể được tính toán chính xác.closed form expression for the partition function up until now, but it has both asymptotic expansions(Ramanujan's work) that accurately approximate it and recurrence relations(euler's work) by which it can be calculated exactly.

Một phương pháp có thể là sử dụng một chức năng tạo. Nói một cách đơn giản, chúng tôi muốn một đa thức có hệ số $ x^n $ sẽ cho chúng tôi $ p (n) $. Nó thực sự khá dễ dàng để tìm thấy chức năng tạo.generating function. In simple terms we want a polynomial whose coefficient of $x^n$ will give us $p(n)$. It is actually quite easy to find the generating function.

$$ \ sum_ {n = 0}^{\ infty} p (n) x^n = \ pi_ {j = 0}^{\ infty} \ sum_ {i = 0}^{\ infty} x^{ji } = \ Pi_ {j = 1}^{\ infy} \ frac {1} {1-x^j} $$

Điều này cũng có thể được viết là:

$$ \ sum_ {n = 0}^{\ infty} p (n) x^n = \ frac {1} {(1-x)} \ frac {1} {(1-x^2)} {1} {(1-x^3)} \ cdots = (1+x^1+x^2+\ cdots+x^r+\ cdots) (1+x^2+x^4+\ cdot ^{2r}+\ cdots) \ cdots $$

Mỗi trong số $ này (1+x^k+x^{2K}+\ cdots+x^{rk}+\ cdots) $ được gọi là sê-ri phụ.

Chúng ta có thể sử dụng điều này để tìm số phân vùng của bất kỳ $ n $ nào. Hãy xem một ví dụ cho $ n = 7 $. Có 2 bước đơn giản.

1. Đầu tiên viết đa thức sao cho công suất tối đa của chuỗi phụ nhỏ hơn hoặc bằng $ n $. Ví dụ, nếu $ n = 7 $, thì đa thức là $ (1+x+x^2+x^3+x^4+x^5+x^6+x^7) (1+x^ 2+x^4+x^6) (1+x^3+x^6) (1+x^4) (1+x^5) (1+x^6) (1+x^7) $ .
2. Bây giờ, chúng tôi đơn giản hóa điều này và tìm hệ số $ x^n $. Trong quá trình này, chúng tôi tìm thấy các số phân vùng cho tất cả $ r

Vì vậy, ví dụ của chúng tôi, chúng tôi chỉ có thể mở rộng đa thức được đưa ra trong điểm-1. Bạn có thể làm điều đó bằng tay. Nhưng tôi đã sử dụng thư viện sympy.sympy library.

from sympy import *
x = symbols('x')
a = expand((1+x+x**2+x**3+x**4+x**5+x**6+x**7)*(1+x**2+x**4+x**6)*(1+x**3+x**6)*(1+x**4)*(1+x**5)*(1+x**6)*(1+x**7))
print(a)
#Output: x**41 + x**40 + 2*x**39 + 3*x**38 + 5*x**37 + 7*x**36 + 11*x**35 + 15*x**34 + 18*x**33 + 24*x**32 + 30*x**31 + 37*x**30 + 44*x**29 + 52*x**28 + 57*x**27 + 64*x**26 + 71*x**25 + 77*x**24 + 81*x**23 + 84*x**22 + 84*x**21 + 84*x**20 + 84*x**19 + 81*x**18 + 77*x**17 + 71*x**16 + 64*x**15 + 57*x**14 + 52*x**13 + 44*x**12 + 37*x**11 + 30*x**10 + 24*x**9 + 18*x**8 + 15*x**7 + 11*x**6 + 7*x**5 + 5*x**4 + 3*x**3 + 2*x**2 + x + 1

Các hệ số của $ x^k $ cho $ p (k) $ chính xác lên đến $ k = 7 $. Vì vậy, từ $ P này (7) = 15 $, $ P (6) = 11 $, v.v. Nhưng với $ n> 7 $, các hệ số sẽ nhỏ hơn $ p (n) $, làm ví dụ $ p (8) = 22 $ nhưng ở đây hệ số là $ 18 $. Để tính toán $ P (8) $, chúng ta cần lấy sê-ri phụ với nguồn $ 8 $ hoặc ít hơn. $x^k$ gives $p(k)$ correctly up to $k = 7$. So, from this $p(7) = 15$, $p(6)=11$ and so on. But for $n>7$, the coefficients will be less than $p(n)$, as an example $p(8)=22$ but here the coefficient is $18$. To calculate $p(8)$, we need to take sub-series with power $8$ or less.

Mặc dù phương pháp này là tốt, nhưng nó khá dài. Nhưng phương pháp này có thể được sửa đổi để tạo ra một mối quan hệ tái phát.recurrence relation.

Định lý Lầu năm góc của Euler cho chúng ta một mối quan hệ để tìm ra đa thức của sản phẩm của sê-ri phụ. Mối quan hệ là:

$$ \ pi_ {i = 1}^{\ infty} (1-x^n) = 1 + \ sum_ {k = 1}^{\ infy} (-1)^k \ lớn (x^{k \ frac {(3K + 1)} {2}} + x^{k \ frac {(3K-1)} {2}} \ lớn) $$

Sử dụng phương trình này, chúng ta có được mối quan hệ tái phát,

$$ p (n) = p (n-1) + p (n-2)-p (n-5)-p (n-7) + \ cdots = \ sum_ {k = 1}^{n} \ Bigg (p \ bigg (n- \ frac {k (3k-1)} {2} \ bigg) + p \ bigg (n- \ frac {k (3k + 1)} {2} \ bigg) \ bigg) $$

Các số $ 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, \ cdots $, được gọi là số năm góc. Chúng tôi tạo ra các số này bằng $ \ frac {k (3k+1)} {2} $ và $ \ frac {k (3K-1)} {2} $.pentagonal numbers. We generate these numbers by $\frac{k(3k+1)}{2}$ and $\frac{k(3k-1)}{2}$.

Hãy cố gắng tìm $ P (7) $, sử dụng cái này.

Sử dụng thuật toán đơn giản này, chúng ta có thể viết mã để lấy số phân vùng.

def par(n):
	summ = 0
	if n == 0 or n == 1:
		result = 1
	else:
		for k in range(1,n+1):
			d1 = n - int((k*(3*k-1))/2)
			d2 = n - int((k*(3*k+1))/2)
			sign = pow(-1,k+1)
			summ = summ + sign*(par(d1) + par(d2))
		result = summ
	return result

Đây là mã để tạo số phân vùng. Điều này không hiệu quả vì nó sử dụng tái phát. Đối với số lượng lớn, nó sẽ mất một lượng lớn thời gian. Trong trình toán học, chúng ta có thể thấy đó là sơ đồ khối.

Vì vậy, chúng tôi đã thấy chức năng đơn giản này. Bây giờ, hãy xác định một người bằng công thức của Euler nhưng theo một cách khác. Để hiểu thuật toán đã sử dụng xem này: Giải thícheuler's formula but in a different manner. To understand the used algorithm watch this: Explanation

def partition(n):
    odd_pos = []; even_pos= []; pos_d = []
    for i in range(1,n+1):
        even_pos.append(i)
        odd_pos.append(2*i+1)
    m = 0; k = 0
    for i in range(n-1):
        if i % 2 == 0:
            pos_d.append(even_pos[m])
            m += 1
        else:
            pos_d.append(odd_pos[k])
            k += 1
    initial = 1; pos_index = [initial]; count = 1
    for i in pos_d:
        d = initial + i
        pos_index.append(d)
        initial = d
        count += 1
        if count > n:
            break
    sign = []
    for i in range(n):
        if i % 4 == 2 or i % 4 == 3:
            sign.append(-1)
        else:
            sign.append(1)
    pos_sign = []; k = 0
    for i in range(1,n+1):
        if i in pos_index:
            ps = (i,sign[k])
            k = k + 1
            pos_sign.append(ps)
        else:
            pos_sign.append(0)
    if len(pos_sign) != n:
        print("Error in position and sign list.")
    partition = [1]
    f_pos = []
    for i in range(n):
        if pos_sign[i]:
            f_pos.append(pos_sign[i])
        partition.append(sum(partition[-p]*s for p,s in f_pos))
    return partition

Đây là mã. Điều này rất hiệu quả. Hãy thử chạy chức năng này.

Lưu ý: Hàm này trả về một danh sách chứa tất cả $ p (n) $ trong phạm vi $ 0 $ đến $ n $.

Như bạn có thể thấy trong chương trình, trong [3] đưa ra một danh sách $ [p (0), p (1), p (2), p (3), p (4), p (5)] $. Do đó, để có được $ p (n) $ bằng cách sử dụng chức năng này, chỉ cần thêm $ [-1] $ vì nó đưa ra phần tử cuối cùng của danh sách.

Chúng ta có thể sử dụng một chương trình đơn giản để vẽ đồ thị.

import matplotlib.pyplot as plt
n = 5
x_vals = [i for i in range(n+1)]
y_vals = partition(n)
plt.grid(color='purple',linestyle='--')
plt.ylabel("Partition Number")
plt.xlabel("Numbers")
plt.step(x_vals,y_vals,c="Black")
plt.savefig("Parti_5.png",bbox_inches = 'tight',dpi = 300)
plt.show()

Đầu ra được đưa ra dưới đây. Đầu ra là một chức năng bước như nó nên được.

Đây là tất cả cho ngày hôm nay. Tôi hy vọng bạn đã học được một cái gì đó mới. Nếu bạn thấy nó hữu ích, thì hãy chia sẻ.

Tác giả: Kazi Abu Rousan: Kazi Abu Rousan

Nhà toán học thuần túy, giống như nhạc sĩ, là người tạo ra thế giới đẹp của mình.

Bertrand Russell

Hôm nay chúng ta sẽ thảo luận về một trong những ý tưởng hấp dẫn nhất về lý thuyết số, rất đơn giản để hiểu nhưng rất phức tạp để tham gia. Hôm nay chúng ta sẽ thấy cách tìm số phân vùng của bất kỳ số nguyên dương $ n $.Partition Number of any positive integer $n$.

Giống như mọi blog, trọng tâm chính của chúng tôi sẽ là viết một chương trình để tìm phân vùng bằng Python. Nhưng hôm nay chúng tôi sẽ sử dụng một điều rất đặc biệt, chúng tôi sẽ sử dụng Thanh tra toán học - một môi trường lập trình trực quan. Nó sử dụng mã python bình thường, nhưng nó có thể hiển thị cho bạn trực quan (biểu diễn khối) của mã bằng cách sử dụng một thứ gọi là trình soạn thảo nút. Đây là một video để hiển thị tính năng của nó.Math Inspector - A visual programming environment. It uses normal python code, but it can show you visual (block representation) of the code using something called Node Editor. Here is a video to show it's feature.

Đẹp phải không? Hãy bắt đầu cuộc thảo luận của chúng tôi.

Số phân vùng là gì?

Trong lý thuyết số, một phân vùng của số nguyên dương $ n $, còn được gọi là phân vùng số nguyên, là một cách viết $ n $ như một tổng số nguyên dương (hai tổng chỉ khác nhau theo thứ tự của bản tóm tắt của chúng được coi là giống nhau Phân vùng, tức là, $ 2+ 4 = 4+ 2 $). Số phân vùng của $ n $ được viết là $ p (n) $Partition of a positive integer $n$, also called an Integer Partition, is a way of writing $n$ as a sum of positive integers (two sums that differ only in the order of their summands are considered the same partition, i.e., $2+4 = 4+ 2$). The partition number of $n$ is written as $p(n)$

Ví dụ, hãy lấy số $ 5 $. Đó là phân vùng là;

$$ 5 = 5 +0 \ \ \ \ \\ = 4 + 1 \ \ \ \ \\ = 3 + 2 \ \ \ \ \ \ = 3 + 1+ 1 \ \ \ \ \\ = 2+1+1+1 \ \\ = 1+1+1+1+1 $$

Do đó, $ P (5) = 7 $. Dễ dàng phải không ?, Hãy xem phân vùng của tất cả các số từ $ 0 $ đến $ 6 $.

Lưu ý: Số phân vùng là $ 0 $ được lấy là $ 1 $.: The partition number of $0$ is taken as $1$.

Xem mức độ dễ dàng của nó không hiểu ý nghĩa của điều này và bạn có thể dễ dàng tìm thấy các phân vùng của các số nhỏ bằng tay. Nhưng những gì về số lượng lớn ?, Giống như $ P (200) $?

Tìm số phân vùng

Không có công thức đơn giản cho số phân vùng. Chúng tôi thường sử dụng đệ quy nhưng nếu bạn chỉ muốn một công thức tạo ra số phân vùng của bất kỳ số nguyên $ n $, thì bạn phải sử dụng công thức kinh hoàng này:Partition Number. We normally use recursion but if you want just a formula which generate partition number of any integer $n$, then you have to use this horrifying formula:

Chỉ cần nhìn vào điều này có thể cho bạn cơn ác mộng. Vì vậy, có bất kỳ phương pháp nào khác không ?, Vâng.

Mặc dù, không có bất kỳ biểu thức hình thức đóng nào cho chức năng phân vùng cho đến bây giờ, nhưng nó có cả hai mở rộng tiệm cận (công việc của Ramanujan) gần đúng với các mối quan hệ nó và tái phát (công việc của Euler) mà nó có thể được tính toán chính xác.closed form expression for the partition function up until now, but it has both asymptotic expansions(Ramanujan's work) that accurately approximate it and recurrence relations(euler's work) by which it can be calculated exactly.

Một phương pháp có thể là sử dụng một chức năng tạo. Nói một cách đơn giản, chúng tôi muốn một đa thức có hệ số $ x^n $ sẽ cho chúng tôi $ p (n) $. Nó thực sự khá dễ dàng để tìm thấy chức năng tạo.generating function. In simple terms we want a polynomial whose coefficient of $x^n$ will give us $p(n)$. It is actually quite easy to find the generating function.

$$ \ sum_ {n = 0}^{\ infty} p (n) x^n = \ pi_ {j = 0}^{\ infty} \ sum_ {i = 0}^{\ infty} x^{ji } = \ Pi_ {j = 1}^{\ infy} \ frac {1} {1-x^j} $$

Điều này cũng có thể được viết là:

$$ \ sum_ {n = 0}^{\ infty} p (n) x^n = \ frac {1} {(1-x)} \ frac {1} {(1-x^2)} {1} {(1-x^3)} \ cdots = (1+x^1+x^2+\ cdots+x^r+\ cdots) (1+x^2+x^4+\ cdot ^{2r}+\ cdots) \ cdots $$

Mỗi trong số $ này (1+x^k+x^{2K}+\ cdots+x^{rk}+\ cdots) $ được gọi là sê-ri phụ.

Chúng ta có thể sử dụng điều này để tìm số phân vùng của bất kỳ $ n $ nào. Hãy xem một ví dụ cho $ n = 7 $. Có 2 bước đơn giản.

1. Đầu tiên viết đa thức sao cho công suất tối đa của chuỗi phụ nhỏ hơn hoặc bằng $ n $. Ví dụ, nếu $ n = 7 $, thì đa thức là $ (1+x+x^2+x^3+x^4+x^5+x^6+x^7) (1+x^ 2+x^4+x^6) (1+x^3+x^6) (1+x^4) (1+x^5) (1+x^6) (1+x^7) $ .
2. Bây giờ, chúng tôi đơn giản hóa điều này và tìm hệ số $ x^n $. Trong quá trình này, chúng tôi tìm thấy các số phân vùng cho tất cả $ r

Vì vậy, ví dụ của chúng tôi, chúng tôi chỉ có thể mở rộng đa thức được đưa ra trong điểm-1. Bạn có thể làm điều đó bằng tay. Nhưng tôi đã sử dụng thư viện sympy.sympy library.

from sympy import *
x = symbols('x')
a = expand((1+x+x**2+x**3+x**4+x**5+x**6+x**7)*(1+x**2+x**4+x**6)*(1+x**3+x**6)*(1+x**4)*(1+x**5)*(1+x**6)*(1+x**7))
print(a)
#Output: x**41 + x**40 + 2*x**39 + 3*x**38 + 5*x**37 + 7*x**36 + 11*x**35 + 15*x**34 + 18*x**33 + 24*x**32 + 30*x**31 + 37*x**30 + 44*x**29 + 52*x**28 + 57*x**27 + 64*x**26 + 71*x**25 + 77*x**24 + 81*x**23 + 84*x**22 + 84*x**21 + 84*x**20 + 84*x**19 + 81*x**18 + 77*x**17 + 71*x**16 + 64*x**15 + 57*x**14 + 52*x**13 + 44*x**12 + 37*x**11 + 30*x**10 + 24*x**9 + 18*x**8 + 15*x**7 + 11*x**6 + 7*x**5 + 5*x**4 + 3*x**3 + 2*x**2 + x + 1

Các hệ số của $ x^k $ cho $ p (k) $ chính xác lên đến $ k = 7 $. Vì vậy, từ $ P này (7) = 15 $, $ P (6) = 11 $, v.v. Nhưng với $ n> 7 $, các hệ số sẽ nhỏ hơn $ p (n) $, làm ví dụ $ p (8) = 22 $ nhưng ở đây hệ số là $ 18 $. Để tính toán $ P (8) $, chúng ta cần lấy sê-ri phụ với nguồn $ 8 $ hoặc ít hơn. $x^k$ gives $p(k)$ correctly up to $k = 7$. So, from this $p(7) = 15$, $p(6)=11$ and so on. But for $n>7$, the coefficients will be less than $p(n)$, as an example $p(8)=22$ but here the coefficient is $18$. To calculate $p(8)$, we need to take sub-series with power $8$ or less.

Mặc dù phương pháp này là tốt, nhưng nó khá dài. Nhưng phương pháp này có thể được sửa đổi để tạo ra một mối quan hệ tái phát.recurrence relation.

Định lý Lầu năm góc của Euler cho chúng ta một mối quan hệ để tìm ra đa thức của sản phẩm của sê-ri phụ. Mối quan hệ là:

$$ \ pi_ {i = 1}^{\ infty} (1-x^n) = 1 + \ sum_ {k = 1}^{\ infy} (-1)^k \ lớn (x^{k \ frac {(3K + 1)} {2}} + x^{k \ frac {(3K-1)} {2}} \ lớn) $$

Sử dụng phương trình này, chúng ta có được mối quan hệ tái phát,

$$ p (n) = p (n-1) + p (n-2)-p (n-5)-p (n-7) + \ cdots = \ sum_ {k = 1}^{n} \ Bigg (p \ bigg (n- \ frac {k (3k-1)} {2} \ bigg) + p \ bigg (n- \ frac {k (3k + 1)} {2} \ bigg) \ bigg) $$

Các số $ 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, \ cdots $, được gọi là số năm góc. Chúng tôi tạo ra các số này bằng $ \ frac {k (3k+1)} {2} $ và $ \ frac {k (3K-1)} {2} $.pentagonal numbers. We generate these numbers by $\frac{k(3k+1)}{2}$ and $\frac{k(3k-1)}{2}$.

Hãy cố gắng tìm $ P (7) $, sử dụng cái này.

Sử dụng thuật toán đơn giản này, chúng ta có thể viết mã để lấy số phân vùng.

def par(n):
	summ = 0
	if n == 0 or n == 1:
		result = 1
	else:
		for k in range(1,n+1):
			d1 = n - int((k*(3*k-1))/2)
			d2 = n - int((k*(3*k+1))/2)
			sign = pow(-1,k+1)
			summ = summ + sign*(par(d1) + par(d2))
		result = summ
	return result

Đây là mã để tạo số phân vùng. Điều này không hiệu quả vì nó sử dụng tái phát. Đối với số lượng lớn, nó sẽ mất một lượng lớn thời gian. Trong trình toán học, chúng ta có thể thấy đó là sơ đồ khối.

Vì vậy, chúng tôi đã thấy chức năng đơn giản này. Bây giờ, hãy xác định một người bằng công thức của Euler nhưng theo một cách khác. Để hiểu thuật toán đã sử dụng xem này: Giải thícheuler's formula but in a different manner. To understand the used algorithm watch this: Explanation

def partition(n):
    odd_pos = []; even_pos= []; pos_d = []
    for i in range(1,n+1):
        even_pos.append(i)
        odd_pos.append(2*i+1)
    m = 0; k = 0
    for i in range(n-1):
        if i % 2 == 0:
            pos_d.append(even_pos[m])
            m += 1
        else:
            pos_d.append(odd_pos[k])
            k += 1
    initial = 1; pos_index = [initial]; count = 1
    for i in pos_d:
        d = initial + i
        pos_index.append(d)
        initial = d
        count += 1
        if count > n:
            break
    sign = []
    for i in range(n):
        if i % 4 == 2 or i % 4 == 3:
            sign.append(-1)
        else:
            sign.append(1)
    pos_sign = []; k = 0
    for i in range(1,n+1):
        if i in pos_index:
            ps = (i,sign[k])
            k = k + 1
            pos_sign.append(ps)
        else:
            pos_sign.append(0)
    if len(pos_sign) != n:
        print("Error in position and sign list.")
    partition = [1]
    f_pos = []
    for i in range(n):
        if pos_sign[i]:
            f_pos.append(pos_sign[i])
        partition.append(sum(partition[-p]*s for p,s in f_pos))
    return partition

Đây là mã. Điều này rất hiệu quả. Hãy thử chạy chức năng này.

Lưu ý: Hàm này trả về một danh sách chứa tất cả $ p (n) $ trong phạm vi $ 0 $ đến $ n $.

Như bạn có thể thấy trong chương trình, trong [3] đưa ra một danh sách $ [p (0), p (1), p (2), p (3), p (4), p (5)] $. Do đó, để có được $ p (n) $ bằng cách sử dụng chức năng này, chỉ cần thêm $ [-1] $ vì nó đưa ra phần tử cuối cùng của danh sách.

Chúng ta có thể sử dụng một chương trình đơn giản để vẽ đồ thị.

import matplotlib.pyplot as plt
n = 5
x_vals = [i for i in range(n+1)]
y_vals = partition(n)
plt.grid(color='purple',linestyle='--')
plt.ylabel("Partition Number")
plt.xlabel("Numbers")
plt.step(x_vals,y_vals,c="Black")
plt.savefig("Parti_5.png",bbox_inches = 'tight',dpi = 300)
plt.show()

Đầu ra được đưa ra dưới đây. Đầu ra là một chức năng bước như nó nên được.

Đây là tất cả cho ngày hôm nay. Tôi hy vọng bạn đã học được một cái gì đó mới. Nếu bạn thấy nó hữu ích, thì hãy chia sẻ.

Đối tác kiến ​​thức

Cheenta là một đối tác tri thức của Học viện Giáo dục Aditya Birla

Học viện Cheenta

Học viện Giáo dục Aditya Birla

Cheenta. Đam mê toán học

Khoa học toán học nâng cao. Được dạy bởi Olympian, các nhà nghiên cứu và bậc thầy thực sự của chủ đề này.

Tham gia thử nghiệm

Chương trình học thuật

Tài nguyên miễn phí

Tại sao Cheenta?

Đóng menu