python - 分布的迭代排列

Question

我正在尝试生成各种分布的所有可能组合。

例如，假设您有 5 点可用于 4 个类别，但您最多只能在任何给定类别上花费 2 点。
在这种情况下，所有可能的解决方案如下:

[0, 1, 2, 2]
[0, 2, 1, 2]
[0, 2, 2, 1]
[1, 0, 2, 2]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 2, 0, 2]
[1, 2, 1, 1]
[1, 2, 2, 0]
[2, 0, 1, 2]
[2, 0, 2, 1]
[2, 1, 0, 2]
[2, 1, 1, 1]
[2, 1, 2, 0]
[2, 2, 0, 1]
[2, 2, 1, 0]

我已经成功地制作了一个递归函数来实现这一点，但是对于大量的类别，它需要很长时间才能生成。我试图制作一个迭代函数，希望能加快它的速度，但我似乎无法让它考虑到类别最大值。

这是我的递归函数(count = 点，dist = 零填充数组，大小与 max_allo 相同)

def distribute_recursive(count, max_allo, dist, depth=0):
    for ration in range(max(count - sum(max_allo[depth + 1:]), 0), min(count, max_allo[depth]) + 1):
        dist[depth] = ration
        count -= ration
        if depth + 1 < len(dist):
            distribute_recursive(count, max_allo, dist, depth + 1)
        else:
            print(dist)
        count += ration

Answer 1

递归并不慢

递归并不是让它变慢的原因。考虑一个更好的算法

def dist (count, limit, points, acc = []):
  if count is 0:
    if sum (acc) is points:
      yield acc
  else:
    for x in range (limit + 1):
      yield from dist (count - 1, limit, points, acc + [x])

您可以在列表中收集生成的结果

print (list (dist (count = 4, limit = 2, points = 5)))

修剪无效组合

上面，我们使用 limit + 1 的固定范围，但是请注意如果我们生成与(例如) limit = 2 的组合会发生什么和 points = 5 ...

[ 2, ... ]    # 3 points remaining
[ 2, 2, ... ] # 1 point remaining

此时，使用固定范围 limit + 1 ( [ 0, 1, 2 ] ) 是愚蠢的，因为我们知道我们只剩下 1 点可以花费。这里唯一剩下的选项是 0或 1 ...

[ 2, 2, 1 ... ] # 0 points remaining

上面我们知道我们可以使用 [ 0 ] 的空范围因为没有积分可以花。这将阻止我们尝试验证组合，例如

[ 2, 2, 2, ... ] # -1 points remaining
[ 2, 2, 2, 0, ... ] # -1 points remaining
[ 2, 2, 2, 1, ... ] # -2 points remaining
[ 2, 2, 2, 2, ... ] # -3 points remaining

如果 count非常大，这可以排除大量无效组合

[ 2, 2, 2, 2, 2, 2, 2, 2, 2, ... ] # -15 points remaining 

为了实现这种优化，我们可以在 dist 中添加另一个参数。函数，但是在 5 个参数处，它会开始看起来很乱。相反，我们引入了一个辅助函数来控制 loop .添加我们的优化，我们将固定范围换成 min (limit, remaining) + 1 的动态范围。 .最后，由于我们知道分配了多少点，我们不再需要测试 sum每种组合；从我们的算法中删除了另一个昂贵的操作

# revision: prune invalid combinations
def dist (count, limit, points):
  def loop (count, remaining, acc):
    if count is 0:
      if remaining is 0:
        yield acc
    else:
      for x in range (min (limit, remaining) + 1):
        yield from loop (count - 1, remaining - x, acc + [x])
  yield from loop (count, points, [])

基准

在下面的基准测试中，我们程序的第一个版本被重命名为 dist1以及使用动态范围的更快程序 dist2 .我们设置了三个测试， small , medium , 和 large

def small (prg):
  return list (prg (count = 4, limit = 2, points = 5))

def medium (prg):
  return list (prg (count = 8, limit = 3, points = 7))

def large (prg):
  return list (prg (count = 16, limit = 5, points = 10))

现在我们运行测试，将每个程序作为参数传递。 large 的注释测试，只有 1 次通过 dist1需要一段时间才能生成结果

print (timeit ('small (dist1)', number = 10000, globals = globals ()))
print (timeit ('small (dist2)', number = 10000, globals = globals ()))

print (timeit ('medium (dist1)', number = 100, globals = globals ()))
print (timeit ('medium (dist2)', number = 100, globals = globals ()))

print (timeit ('large (dist1)', number = 1, globals = globals ()))
print (timeit ('large (dist2)', number = 1, globals = globals ()))

small 的结果测试表明，修剪无效组合并没有太大的区别。然而在 medium和 large情况下，差异是巨大的。我们的旧程序需要 30 多分钟才能完成大型集，但使用新程序只需 1 秒多一点!

dist1 small      0.8512216459494084
dist2 small      0.8610155049245805   (0.98x speed-up)

dist1 medium     6.142372329952195
dist2 medium     0.9355670949444175   (6.57x speed-up)

dist1 large   1933.0877765258774
dist2 large      1.4107366011012346   (1370.26x speed-up)

作为引用框架，每个结果的大小打印在下面

print (len (small (dist2)))   # 16      (this is the example in your question)
print (len (medium (dist2)))  # 2472
print (len (large (dist2)))   # 336336

检查我们的理解

在 large使用 count = 12 进行基准测试和 limit = 5 ，使用我们未优化的程序，我们迭代了 512 或 244,140,​​625 种可能的组合。使用我们优化的程序，我们跳过所有无效组合，从而产生 336,336 个有效答案。通过单独分析组合计数，我们发现 99.86% 的可能组合是无效的。如果对每个组合的分析花费相同的时间，由于无效的组合剪枝，我们可以预期优化后的程序的性能至少提高 725.88 倍。

在 large基准测试，以 1370.26 倍的速度测量，优化后的程序满足了我们的期望，甚至超出了我们的预期。额外的加速可能是由于我们取消了对 sum 的调用。

huuuuge

为了证明这种技术适用于非常大的数据集，请考虑 huge基准。我们的程序在 716 种或 33,232,930,569,601 种可能性中找到 17,321,844 个有效组合。

在这个测试中，我们优化的程序修剪了 99.99479% 的无效组合。将这些数字与之前的数据集相关联，我们估计优化后的程序运行速度比未优化版本快 1,918,556.16 倍。

该基准使用未优化程序的理论运行时间为 117.60 岁 .优化后的程序只需 1 多分钟即可找到答案。

def huge (prg):
  return list (prg (count = 16, limit = 7, points = 12))

print (timeit ('huge (dist2)', number = 1, globals = globals ()))
# 68.06868170504458

print (len (huge (dist2)))
# 17321844