Partitionen von k Teilen mit minimalen und maximalen Teilwerten

Question

Wie erzeuge ich die Partitionen einer Zahl, die genau k Teile haben, wobei jedes Teil einen minimalen und maximalen Wert hat?

Zum Beispiel, wenn ich will alle Partitionen von 21 mit 6 Teilen mit minimalem Teilwert 3 und dem maximalen Teilwert wählen 6, soll ich die folgenden Partitionen erhalten:

[3, 3, 3, 3, 3, 6]  
[3, 3, 3, 3, 4, 5] 
[3, 3, 3, 4, 4, 4] 

ich folgenden habe aufsteigend Partition Code, mit freundlicher Genehmigung von http://jeromekelleher.net/generating-integer-partitions.html

def accel_asc(n): 
    a = [0 for i in range(n + 1)] 
    k = 1 
    y = n - 1 
    while k != 0: 
     x = a[k - 1] + 1 
     k -= 1 
     while 2 * x <= y: 
      a[k] = x 
      y -= x 
      k += 1 
     l = k + 1 
     while x <= y: 
      a[k] = x 
      a[l] = y 
      yield a[:k + 2] 
      x += 1 
      y -= 1 
     a[k] = x + y 
     y = x + y - 1 
     yield a[:k + 1] 

und ein einfaches fuction ich nur die Partitionen zu bekommen habe ich von der Funktion oben wollen:

def eligible_partitions(list_of_partitions, min_value, max_value, k): 
    l = [] 
    for x in list_of_partitions: 
      if min(x) >= min_value and max(x) <= max_value and len(x) == k: 
       l.append(x) 
    return l 

Anstatt alle Partitionen eines bestimmten Werts generieren und durchlaufen zu müssen, möchte ich nur diejenigen generieren, die die angegebenen Kriterien erfüllen.

Answer 1

Hier ist eine Möglichkeit, es zu tun:

def part(x, n, minval, maxval): 
    if not n * minval <= x <= n * maxval: 
    return 
    elif n == 0: 
    yield [] 
    else: 
    for val in range(minval, maxval + 1): 
     for p in part(x - val, n - 1, val, maxval): 
     yield [val] + p 

for p in part(21, 6, 3, 6): 
    print p 

Dies erzeugt:

[3, 3, 3, 3, 3, 6] 
[3, 3, 3, 3, 4, 5] 
[3, 3, 3, 4, 4, 4]