Oct-15-2017, 07:09 PM
Hello all.
This is my first post, so if this question is not appropriate for this forum please let me know and I will remove it. If it remains, formatting help would be appreciated.
The following code produces the triangular array, T(n,k), of partitions of n into k positive parts, 1<=k<=n:
[1]
[1, 1]
[1, 1, 1]
[1, 2, 1, 1]
[1, 2, 2, 1, 1]
[0, 3, 3, 0, 0, 0]
[0, 0, 4, 0, 0, 0, 0]
[0, 0, 0, 5, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Rows 1-5 are complete and rows 6-10, clearly, are not. To confirm the first 5 rows are correct, see https://oeis.org/A008284.
What I hope to do is (1) flatten the triangular array into a linear array, and then (2) eliminate the wasted memory (the zeros) via proper array indexing. (2) is the where this gets confusing.
Is this of interest to anyone?
This is my first post, so if this question is not appropriate for this forum please let me know and I will remove it. If it remains, formatting help would be appreciated.
The following code produces the triangular array, T(n,k), of partitions of n into k positive parts, 1<=k<=n:
from math import * n = 10 #We need an array of size 2n, because the triangle is complete only up to nth row. m = 2*n tri = [] halfn = int(ceil(float(m)/2.0)) #Initialize array to zeros (so that we know no completed row contains an error). for i in range(0,m): tri.append([0 for k in range(i+1)]) #Initialize first two rows. tri[0][0] = 1 tri[1][0] = 1 tri[1][1] = 1 #Fill in the triangle by cumulatively adding the elements of the previous #row and placing the result diagonally (parallel to hypotenuse). Complete #the nth row by appending the "tail" of the previous row. for i in range(2,halfn): #Reset sum for each new row. sums = 0 #The list of values of previous row. prev = tri[i-1] row = i #Place summands diagonally... for col in range(0,len(prev)): sums += prev[col] tri[row][col] = sums row += 1 col += 1 #Now append the "tail" of the previous row to complete this row. for k in range(tri[i][1], len(prev) + 1): tri[i][k] = prev[k-1] #change n to m to print entire triangle. for i in range(0,n): print(("%d" % (i+1), tri[i]))Currently, about half of the allocated memory is wasted space. For example, with n = 5, after execution the triangle looks like this:
[1]
[1, 1]
[1, 1, 1]
[1, 2, 1, 1]
[1, 2, 2, 1, 1]
[0, 3, 3, 0, 0, 0]
[0, 0, 4, 0, 0, 0, 0]
[0, 0, 0, 5, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Rows 1-5 are complete and rows 6-10, clearly, are not. To confirm the first 5 rows are correct, see https://oeis.org/A008284.
What I hope to do is (1) flatten the triangular array into a linear array, and then (2) eliminate the wasted memory (the zeros) via proper array indexing. (2) is the where this gets confusing.
Is this of interest to anyone?