我的问题是：我想找到n个可能数字的所有m个长度组合，以使数字的平均值大于阈值X。
例如，假设长度n=3和数字是{1, 2}，阈值是1.5。允许的总组合为2*2*2 == 2**3 = 8即
222 - avg 2.000000 > 1.500000 -> include in acceptable set
221 - avg 1.666667 > 1.500000 -> include in acceptable set
212 - avg 1.666667 > 1.500000 -> include in acceptable set
211 - avg 1.333333 < 1.500000 -> adding 1 and below to the exclude list
122 - avg 1.666667 > 1.500000 -> include in acceptable set
121 - avg 1.333333 < 1.500000 -> skipping this vote combo
112 - avg 1.333333 < 1.500000 -> skipping this vote combo
111 - avg 1.000000 < 1.500000 -> skipping this vote combo
final list of valid votecombos
[[2, 2, 2], [2, 2, 1], [2, 1, 2], [1,2,2]]
我认为，解决此问题的方法是想象一棵所有可能组合的树，然后动态修剪该树以获取不可能的解决方案。例如，想象这样的n=3级树
root
/ \
1 2
/ \ / \
1 2 1 2
/ \ / \ / \ / \
1 2 1 2 1 2 1 2
通往叶子的每条路径都是可能的组合。您可以想象，对于级别n=3和m=5，节点数大约为N == m**n == 5**3 == 125' nodes. Its easy to see that the tree gets really really large even for m = 5 and n = 20`。 96万亿个节点。因此，该树无法存储在内存中。但它也不必一定是因为它非常结构化。
获得所有可能的有效组合的方法是，DFS以一种预定的方式遍历树，但在遍历的同时还继续修剪树。例如，在以上示例中，前三个组合{222, 221, 212}有效，但是211无效。这也意味着从该点开始，任何其他包含两个1的组合都将无效。因此，我们可以用除1以外的根1修剪树的整个左侧部分！这样可以帮助我们避免检查3种组合。
为此，我编写了一个简单的python脚本
import string
import itertools
import numpy as np
import re
chars = '21'
grad_thr = 1.5
seats = 3
excllist = []
validlist = []
for word in itertools.product(chars, repeat = seats):
# form the string of digits
votestr = ''.join(word)
print (votestr)
# convert string into list of chars
liststr = list(votestr)
#print liststr
# map list of chars to list of ints
listint = map(int, liststr)
if len(list(set(listint) & set(excllist))) == 0:
# if there are no excluded votes in this votecombo then proceed
# compute a function over the digits; func can be average/bayesian score/something else.
y_mean = np.mean(listint)
print 'avg %f' %y_mean
#y_bayes = bayesian score
if y_mean >= grad_thr:
# if function result is greater than grad threshold then save result to a list of valid votes
validlist.append(listint)
print 'geq than %f -> include in acceptable set' %grad_thr
elif y_mean < grad_thr:
# if function result is not greater than grad threshold then add logic to stop searching the tree further
# prune unnecessary part of the tree
if listint[-1] not in excllist:
excllist = [int(d) for d in range(listint[-1] + 1)]
print 'adding %d and below to the exclude list' %listint[-1]
else:
print '%d already present in exclude list' %listint[-1]
else:
print 'skipping this vote combo'
print '\nfinal valid list of votecombos'
print validvotelist
print 'exclude list'
print excllist
print '\n'
通过这种方式，我遍历了所有可能的组合，并跳过了计算平均值的过程。但是，进入for循环后，我仍然要检查每个可能的组合。
是否可以完全不检查组合？即我们知道组合121不起作用，但是我们仍然必须进入for循环然后跳过组合。有可能不这样做吗？
参考方案
一些建议：
构建数字的多集而不是有序列表。有序列表的平均值不依赖于其中的数字顺序，每个数字的多集对应于许多有序列表，因此您可以通过仅保留多集并生成所有相应的有序列表来节省大量内存在需要时从他们那里得到。
与其从一个空的多重集开始并通过在每个DFS边缘添加一个数字来构建数字，不如从一个完整的多重集开始，其中包含最高位数的n个副本，在每个DFS边缘，将其中一位减少1。（这是假设优点是我们知道向下穿越DFS边缘只会降低平均值，因此，如果这样做会产生低于阈值的平均值，我们就知道可以完全修剪分支，因为所有更深的后代均必须具有更低的平均值。
实际上，您在任何地方都不需要除法：您要做的就是将阈值x乘以n，从而从一开始就获得一个最小的数字总和，然后您可以将其与多集的总和进行比较。此外，根据先前关于如何生成子代的建议，子代的总和总是比其父代的总和小1，因此我们甚至不需要循环来计算总和-这是一个恒定时间操作。
避免重复
但是，上面（2）中的生成子代的规则确实带来了一个难题：我们如何确保我们不会多次生子？例如。如果我们在树中有一个包含多集{5，8}的节点（在此示例中只是一个简单集），则将生成子节点{4，8}和{5，7}；但是如果我们在树中某处有另一个节点，用于集合{4，9}，则将生成子节点{3，9}和{4，8}-因此子节点{4，8}将生成两次。
解决此问题的方法是找出每个孩子可以“挑选”唯一父母的规则，然后安排事物，以便父母仅生成他们将成为“被挑选”父母的孩子。例如。我们可以说，一个孩子应该选择一个父母作为唯一的父母，在所有可能产生它的父母中，当其元素按升序排列时，在字典上最大。 （您也可以按字典顺序选择最小的字典，但是最大的字典证明计算效率更高。）对于示例多重集{4，8}，可以生成它的两个父级为{5，8}和{4，9} ;其中，{5，8}在字典上较大，因此我们将其选为父项。
但是在DFS期间，我们是从父级生成子级的，而不是相反的，因此，当我们位于某个节点（可能是其他某个节点的父级）时，我们仍然需要将“挑选父级”的规则转换为告诉我们的规则，实际上是该孩子的“挑选”父母。为此，请考虑某个子节点v的所有潜在父代。首先，有几个？如果v具有小于最大数字值的r个不同数字，则存在r个可能的父代，每个父代等于v，但具有1个不同的数字大1。
假设v中的最低位数是d，并且有k> = 1个副本。在v的r个潜在父级中，它们全部也将具有d的k个副本-除了一个父级u具有k-1个副本之外，因为在这个父级中，必须是d + 1位数字减少1到d（从而将d的副本数从k-1增加到k）以生成v。现在，如果我们以数字递增的顺序写出v的r个潜在父代，请注意，除您将从d的k个副本开始，而您从d的k-1个（可能为0）副本开始，然后是d + 1个（至少1个副本）。因此，在字典上，u比v的所有其他r-1个潜在父代大。
从潜在的父节点的角度，这告诉我们成为被选父的标准。假设u中的最小数字为d。然后，当且仅当v可以通过将u中的d位减小为d-1或将u中的（d + 1）位减小为v来形成，某些节点v才将u作为其选择的父级。这转化为生成子代的两个简单而有效的规则：
假设我们在某个节点u处，并希望根据上述规则为DFS生成其所有子级，以便每个满意的多集在树上生成一次。和以前一样，令d为u中的最小数字。然后：
如果d> minimum_digit，则生成与u相同的子级，但u中的d位之一已减小到d-1。示例：{3，3，3，4，6，6}应生成子项{2，3，3，4，6，6}。
如果u包含数字d + 1，请生成与u相同的子代，除了（d + 1）数字之一已减小到d。示例：{3，3，3，4，6，6}应该生成子{3，3，3，3，6，6}。
因此，在以上示例中，节点u = {3，3，3，4，6，6}将生成2个孩子。 （没有节点会生成超过两个子代。）
如果将多集表示为排序列表或按排序顺序表示数字的频率计数，则只需扫描初始段即可有效地检查这两种情况。
例
在您的示例中（请记住，我们仅在此处生成多集；在单独的步骤中生成它们的每个排列以查找所有有序列表）：
sum_threshold = 1.5 * 3 = 4.5
SUM
222 6
/
122 5
/
112 4
PRUNE
在一个稍大的示例中，数字= {1、2、3}，n = 3和x = 0（以显示所有多重集将被生成一次）。
SUM
333 9
/
233 8
/ \
133 223 7
/ \
123 222 6
/ \
113 122 5
\
112 4
\
111 3
由于某些原因，我无法从以下代码中找出原因：>>> from pytz import timezone >>> timezone('America/Chicago') 我得到：<DstTzInfo 'America/Chicago' LMT-1 day, 18:09:00 STD…
R'relaimpo'软件包的Python端口 - python我需要计算Lindeman-Merenda-Gold（LMG）分数，以进行回归分析。我发现R语言的relaimpo包下有该文件。不幸的是，我对R没有任何经验。我检查了互联网，但找不到。这个程序包有python端口吗？如果不存在，是否可以通过python使用该包？ python参考方案 最近，我遇到了pingouin库。
Python:传递记录器是个好主意吗？ - python我的Web服务器的API日志如下：started started succeeded failed 那是同时收到的两个请求。很难说哪一个成功或失败。为了彼此分离请求，我为每个请求创建了一个随机数，并将其用作记录器的名称logger = logging.getLogger(random_number) 日志变成[111] started [222] start…
Python-Excel导出 - python我有以下代码：import pandas as pd import requests from bs4 import BeautifulSoup res = requests.get("https://www.bankier.pl/gielda/notowania/akcje") soup = BeautifulSoup(res.cont…
Matplotlib'粗体'字体 - python跟随this example：import numpy as np import matplotlib.pyplot as plt fig = plt.figure() for i, label in enumerate(('A', 'B', 'C', 'D')): ax = f…