订制企业网站,设计案例分享网站,新乡手机网站建设哪家好,网站设计推广方案优化这种方法的方法不是找出更快的方式来生成排列#xff0c;而是生成尽可能少的排列。
首先#xff0c;如果您只想要按排序顺序的组合#xff0c;您将如何做到这一点#xff1f;
您不需要生成0到100的所有可能组合#xff0c;然后对其进行过滤。第一个数字a可以是0到100之…优化这种方法的方法不是找出更快的方式来生成排列而是生成尽可能少的排列。
首先如果您只想要按排序顺序的组合您将如何做到这一点
您不需要生成0到100的所有可能组合然后对其进行过滤。第一个数字a可以是0到100之间的b任何数字。第二个数字可以是0到100-a之间的任何值。第三个数字c只能是100-ab。所以for a in range(0, 101):
for b in range(0, 101-a):
c 100-a-b
yield a, b, c
现在而不是产生100*100*100组合过滤下来到100*50*11我们只是生成100*50*11为2000X加速。
但是请记住仍有X * (X/2)**N答案。因此X * (X/2)**N及时计算它们而不是X**N最佳 - 但它仍然是指数时间。而且没有办法解决这个问题; 毕竟你想要一个指数的结果。
你可以寻找方法让第一部分itertools.product与reduceor 结合起来更简洁accumulate但我认为它最终会降低可读性并且你希望能够扩展到任意任意N并且还能得到所有的排列而不仅仅是排序的。所以在你这样做之前保持它是可以理解的然后在你完成之后寻找方法来压缩它。
你显然需要经历N步骤。我认为使用递归比循环更容易理解。
当n为1时唯一的组合是(x,)。
否则对于从0到x的每个值a您可以将该值与总和为xa的n-1个数的所有组合一起使用。所以def sum_to_x(x, n):
if n 1:
yield (x,)
return
for a in range(x1):
for result in sum_to_x(x-a, n-1):
yield (a, *result)
现在你只需要添加排列你就完成了def perm_sum_to_x(x, n):
for combi in sum_to_x(x, n):
yield from itertools.permutations(combi)
但是有一个问题permutations置换位置而不是价值。所以如果你有比如说(100, 0, 0)那六个排列是(100, 0, 0)(100, 0, 0)(0, 100, 0)(0, 0, 100)(0, 100, 0)(0, 0, 100)。
如果N非常小 - 就像在你的例子中那样N 3且X 100-可以很好地生成每个组合的所有6个排列并过滤它们def perm_sum_to_x(x, n):
for combi in sum_to_x(x, n):
yield from set(itertools.permutations(combi))
......但如果N能够变大我们也会在那里谈论很多浪费的工作。
这里有很多关于如何在没有重复值的情况下进行排列的好答案。例如请参阅此问题。借用该答案的实现def perm_sum_to_x(x, n):
for combi in sum_to_x(x, n):
yield from unique_permutations(combi)def perm_sum_to_x(x, n):
for combi in sum_to_x(x, n):
yield from sympy.multiset_permutations(combi)
def perm_sum_to_x(x, n):
for combi in sum_to_x(x, n):
yield from more_itertools.distinct_permutations(combi)
