找到所有固定大小的唯一组合以达到给定的平均范围

Question

我有一个整数的范围

big_list = [1, 2, ..., 100]

我需要找到这个范围内所有固定长度的数字子集，它们的平均值在k=50（比如45-55）以内，k=5。e、 我们有一个固定尺寸的6个，平均50个左右

sample = [71, 20, 23, 99, 25, 60]

问题是列表必须是唯一的，没有重复的数字。你知道吗

顺序不重要，所以[71，20，23，99，25，60]和[20，71，23，99，25，60]只是一个组合。你知道吗

我在考虑使用itertools生成所有的组合，并根据我的标准进行筛选。但运行时间将非常糟糕，因为大的数字列表可能从10号到400号不等。你知道吗

如何使用上述条件生成一组列表

Answer 1

秩序是微不足道的。你知道吗

只要用i-th数大于(i-1)-th的约束来安排就行了。在下面的算法中，您通过将left增加1来递归

要得到介于45和55之间的平均值，请考虑递归公式

import math

# left: previous number is left-1
# s: current sum
# d: depth
# c: combination
def fill(left, s, d, c):
  if d == 0:
    return print(c, sum(c)/n)

  # constraint c_sum >= 45*n
  # we look for minimal i such that 
  # sum + i + 100+99+...+(100-(depth-1)+1) >= 45*n
  # sum + i + 100*(d-1) - (d-2)(d-1)/2 >= 45*n
  # i >= 45*n - 100*(d-1) - (d-2)(d-1)/2 - sum
  # 
  # constraint c_sum <= 55*n
  # we look for maximal right such that
  # sum + i + (i+1)+...+(i+(d-1)) <= 55*n
  # sum + (d-1)*i + d(d-1)/2 <= 55*n
  # i <= ( 55*n - d(d-1)/2 - sum )/(d-1)
  minleft = max(left, math.ceil(minBound*n - 100*(d-1) - (d-2)*(d-1)/2 - s))
  if d == 1:
    maxright = min(100, maxBound*n-s)
  else:
    maxright = min(100, math.floor(( maxBound*n - d*(d-1)/2 - s )/(d-1)) )
  for i in range(minleft, maxright+1):
    newsum = s + i
    c[d-1] = i
    fill(i+1, newsum, d-1, c)

n = 6
minBound = 45
maxBound = 55
fill(0, 0, n, [0]*n)

---

在进一步的评论之后，op对上面的组合一点也不感兴趣，而是对所有组合中不能出现两次数字的组合感兴趣

algo可以简化为非常基本的算法：

n = 300
c = list(range(1, n))
while len(c) >= 6:
  print([c.pop(), c.pop(), c.pop(), c.pop(0), c.pop(0), c.pop(0)])

Answer 2

可以对生成器使用递归：

def combo(d, k, c = []):
   if len(c) == 6:
      yield c
   else:
      for i in d:
        _c = (sum(c)+i)/float(len(c)+1)
        if i not in c and (len(c) + 1 < 6 or 50-k <= _c <= 50+k):
            yield from combo(d, k, c+[i])

当然，正如@japreis所指出的，这个问题将产生非常糟糕的最坏情况时间复杂性。不过，一种可能的解决方法是将combo视为迭代器池，只需根据需要在代码的其他地方访问生成的组合。例如，要访问前100个结果：

result = combo(range(1, 100), 5)
for _ in range(100):
   print(next(result))

输出：

[1, 2, 3, 67, 98, 99]
[1, 2, 3, 67, 99, 98]
[1, 2, 3, 68, 97, 99]
[1, 2, 3, 68, 98, 99]
[1, 2, 3, 68, 99, 97]
[1, 2, 3, 68, 99, 98]
[1, 2, 3, 69, 96, 99]
[1, 2, 3, 69, 97, 98]
[1, 2, 3, 69, 97, 99]
[1, 2, 3, 69, 98, 97]
...