如何迭代具有固定總和的陣列集

考慮l范圍內的所有非負整數陣列0,...,m。我只想迭代（使用生成器）那些總和正好是s.

例如， take l=7, s=5, m=4，迭代可能如下所示：

(0, 0, 0, 0, 0, 1, 4)
(0, 0, 0, 0, 0, 2, 3)
(0, 0, 0, 0, 0, 3, 2)
(0, 0, 0, 0, 0, 4, 1)
(0, 0, 0, 0, 1, 0, 4)
(0, 0, 0, 0, 1, 1, 3)
(0, 0, 0, 0, 1, 2, 2)
(0, 0, 0, 0, 1, 3, 1)
(0, 0, 0, 0, 1, 4, 0)
[...]
(3, 2, 0, 0, 0, 0, 0)
(4, 0, 0, 0, 0, 0, 1)
(4, 0, 0, 0, 0, 1, 0)
(4, 0, 0, 0, 1, 0, 0)
(4, 0, 0, 1, 0, 0, 0)
(4, 0, 1, 0, 0, 0, 0)
(4, 1, 0, 0, 0, 0, 0)

我不介意迭代發生的順序，但我希望它是有效的。

對于較大的變數值來說，重現上述內容的一種非常愚蠢的方法是：

import itertools
s = 5
l = 7
m = 5
for arr in itertools.product(range(m), repeat=l):
    if sum(arr) == s:
        print(arr)

uj5u.com熱心網友回復：

您要查找的內容稱為“磁區”。不幸的是，對于“磁區”是否是指將集合拆分為多個磁區（例如 [a,b,c] 到 [[a,b],[c]]）存在一些歧義，只是表征每個拆分大小的數字（例如 [2,1])，或者有多少不同的分裂的計數。我發現的最有希望的搜索詞是“將一個數字分成 k 個部分 python”，產生具有給定 k 個磁區的 Python 整數磁區和“不可區分專案的 python 磁區”在 Python 中懶惰地將 N 個專案磁區到 K 個 bin 中。這些答案側重于至少具有一個元素的磁區，而您允許磁區包含零個元素。此外，您似乎關心磁區內的順序。例如，(0, 0, 0, 0, 0, 1, 4)(0, 0, 0, 0, 0, 4, 1)，并(0, 0, 0, 0, 1, 0, 4)作為不同的磁區，而傳統上這些被認為是等效的。

我認為最好的方法是遍歷桶，并為每個桶遍歷可能的值。我更改了引數名稱；l、s 和 m 以及資訊量不大的名稱，“sum”和“max”是內置函式。我當前的版本，可能需要更多除錯：

def get_partitions(length, total, upper_bound):
    if length == 1:
        if total > upper_bound:
            return []
        return [[total]]
    if total == 0:
        return [[0]*length]                    
    return [ [n] sub_partition for 
               n in range(min(total, upper_bound) 1) for 
                   sub_partition in get_partitions(
                       length-1, total-n, upper_bound)]   

旁注：我最初將“遍歷陣列”讀作“遍歷陣列的元素”。我認為正確的術語是“迭代一組這樣的陣列”。當您說“迭代 x”時，x 被視為可迭代物件，而不是可迭代物件的元素。

uj5u.com熱心網友回復：

通過修改這個答案，考慮到max_value：

def sums(length, total_sum, max_value):
    if length == 1:
        yield (total_sum,)
    else:
        for value in range(max(0, total_sum - (length - 1) * max_value),
                               min(max_value, total_sum)   1):
            for permutation in sums(length - 1, total_sum - value, max_value):
                yield (value,)   permutation

L = list(sums(7,5, 4))
print('total permutations:',len(L))

# First and last 10 of list
for i in L[:10]   ['...']   L[-10:]:
    print(i)

total permutations: 455
(0, 0, 0, 0, 0, 1, 4)
(0, 0, 0, 0, 0, 2, 3)
(0, 0, 0, 0, 0, 3, 2)
(0, 0, 0, 0, 0, 4, 1)
(0, 0, 0, 0, 1, 0, 4)
(0, 0, 0, 0, 1, 1, 3)
(0, 0, 0, 0, 1, 2, 2)
(0, 0, 0, 0, 1, 3, 1)
(0, 0, 0, 0, 1, 4, 0)
(0, 0, 0, 0, 2, 0, 3)
...
(3, 1, 0, 0, 1, 0, 0)
(3, 1, 0, 1, 0, 0, 0)
(3, 1, 1, 0, 0, 0, 0)
(3, 2, 0, 0, 0, 0, 0)
(4, 0, 0, 0, 0, 0, 1)
(4, 0, 0, 0, 0, 1, 0)
(4, 0, 0, 0, 1, 0, 0)
(4, 0, 0, 1, 0, 0, 0)
(4, 0, 1, 0, 0, 0, 0)
(4, 1, 0, 0, 0, 0, 0)

uj5u.com熱心網友回復：

以這種方式思考問題，您希望s將球放入l桶m中，任何一個桶中都不要超過球。

因為我知道如何一次添加一個球，所以我的直覺是使用遞回來解決這個問題。基本情況是放置0球而不是s從一個步驟到下一個步驟，將 1 個球添加到當前少于m球的每個桶中。

為了確保確實可以完成遞回，我們首先檢查是否有足夠的地方放置球。

# this helper function tells us the last non zero index in an array
def last_non_zero(arr):
  indx = -1
  while arr[indx] == 0 and indx > -len(arr):
    indx -= 1
  return len(arr)   indx


def balls_in_buckets(num_balls, num_buckets, max_balls):
  assert num_buckets * max_balls >= num_balls, f"You can't put {num_balls} balls in {num_buckets} buckets without more than {max_balls} in a bucket." 

  if num_balls == 0:
    yield ([0]*num_buckets).copy()

  else:
    for array in balls_in_buckets(num_balls - 1, num_buckets, max_balls):
      for bucket_number in range(last_non_zero(array), num_buckets):
        if array[bucket_number] < max_balls:
          array_copy = array.copy()
          array_copy[bucket_number]  = 1
          yield array_copy

編輯：添加了洗掉重復項的代碼

編輯：性能改進，生成整個序列大約需要 2 秒l=14, s=10, m=8。序列中有 1,143,870 個專案。

標籤：Python 算法 数学

上一篇：如何重復一個函式？

下一篇：vue函式中未定義變數