Phân vùng tích phân Python với phân vùng k đã cho

Question

Tôi đang cố gắng tìm hoặc phát triển mã phân vùng nguyên phân cho Python.

FYI, Phân tách nguyên phân đại diện cho một số nguyên n cho trước là tổng các số nguyên nhỏ hơn n. Ví dụ: số nguyên 5 có thể được biểu thị dưới dạng 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1

Tôi đã tìm thấy một số giải pháp cho việc này. http://homepages.ed.ac.uk/jkellehe/partitions.php và http://code.activestate.com/recipes/218332-generator-for-integer-partitions/

Tuy nhiên, điều tôi thực sự muốn là hạn chế số lượng phân vùng.

Say, # của phân vùng k = 2, một chương trình chỉ cần hiển thị 5 = 4 + 1 = 3 + 2,

nếu k = 3, 5 = 3 + 1 + 1 = 2 + 2 + 1

Answer 1

Tôi đã viết một giải pháp phát

def partitionfunc(n,k,l=1): 
    '''n is the integer to partition, k is the length of partitions, l is the min partition element size''' 
    if k < 1: 
     raise StopIteration 
    if k == 1: 
     if n >= l: 
      yield (n,) 
     raise StopIteration 
    for i in range(l,n+1): 
     for result in partitionfunc(n-i,k-1,i): 
      yield (i,)+result 

này tạo ra tất cả các phân vùng của n với chiều dài k với mỗi một là theo thứ tự nhất đến lớn nhất.

Chỉ cần lưu ý nhanh: Qua cProfile, có vẻ như sử dụng phương pháp tạo máy phát nhanh hơn nhiều so với phương pháp trực tiếp của falsetru, sử dụng hàm kiểm tra lambda x,y: list(partitionfunc(x,y)). Trong lần chạy thử nghiệm n=50,k-5, mã của tôi chạy trong 0,019 giây so với 2,612 giây của phương pháp trực tiếp.

Answer 2

def part(n, k): 
    def _part(n, k, pre): 
     if n <= 0: 
      return [] 
     if k == 1: 
      if n <= pre: 
       return [[n]] 
      return [] 
     ret = [] 
     for i in range(min(pre, n), 0, -1): 
      ret += [[i] + sub for sub in _part(n-i, k-1, i)] 
     return ret 
    return _part(n, k, n) 

Ví dụ:

>>> part(5, 1) 
[[5]] 
>>> part(5, 2) 
[[4, 1], [3, 2]] 
>>> part(5, 3) 
[[3, 1, 1], [2, 2, 1]] 
>>> part(5, 4) 
[[2, 1, 1, 1]] 
>>> part(5, 5) 
[[1, 1, 1, 1, 1]] 
>>> part(6, 3) 
[[4, 1, 1], [3, 2, 1], [2, 2, 2]] 

CẬP NHẬT

Sử dụng memoization:

def part(n, k): 
    def memoize(f): 
     cache = [[[None] * n for j in xrange(k)] for i in xrange(n)] 
     def wrapper(n, k, pre): 
      if cache[n-1][k-1][pre-1] is None: 
       cache[n-1][k-1][pre-1] = f(n, k, pre) 
      return cache[n-1][k-1][pre-1] 
     return wrapper 

    @memoize 
    def _part(n, k, pre): 
     if n <= 0: 
      return [] 
     if k == 1: 
      if n <= pre: 
       return [(n,)] 
      return [] 
     ret = [] 
     for i in xrange(min(pre, n), 0, -1): 
      ret += [(i,) + sub for sub in _part(n-i, k-1, i)] 
     return ret 
    return _part(n, k, n) 

Answer 3

Đầu tiên tôi muốn cảm ơn tất cả mọi người vì những đóng góp của họ. Tôi đến đây cần một thuật toán để tạo phân vùng số nguyên với các chi tiết sau:

Tạo phân đoạn của một số thành các phần chính xác k nhưng cũng có giới hạn tối thiểu và tối đa.

Vì vậy, tôi sửa đổi mã của "Snakes and Coffee" để phù hợp với những yêu cầu mới:

def partition_min_max(n,k,l, m): 
'''n is the integer to partition, k is the length of partitions, 
l is the min partition element size, m is the max partition element size ''' 
if k < 1: 
    raise StopIteration 
if k == 1: 
    if n <= m and n>=l : 
     yield (n,) 
    raise StopIteration 
for i in range(l,m+1): 
    for result in partition_min_max(n-i,k-1,i,m):     
     yield result+(i,) 


>>> x = list(partition_min_max(20 ,3, 3, 10)) 
>>> print(x) 
>>> [(10, 7, 3), (9, 8, 3), (10, 6, 4), (9, 7, 4), (8, 8, 4), (10, 5, 5), (9, 6, 5), (8, 7, 5), (8, 6, 6), (7, 7, 6)]