解决排列和约束问题

Question

快速明了的时间表优化。举个例子:我可以练习7首不同的歌。我总共有30分钟的练习时间。我可以把它分成5分钟的窗口。所以我可以练习一首歌30分钟，或者6首不同的歌，每首歌5首，或者一首25分钟，一首5分钟，等等。我有一个实用函数，能够计算出最佳配置。

我需要生成所有不同的练习分配。我以前做过这样的事情，“算法”令人反感--我生成了0,5,10,15,20,25,30^7的所有可能的组合，然后丢弃了所有不等于30的行。

粗俗，愚蠢的方法，我知道。我一直在尝试从数学上确定这个问题是什么，然后我应该能够找到一个有效的算法来用Python来解决它。遗憾的是，我无法向谷歌描述得足够好，以至于找不到它。

有没有人能建议这个问题的类别或合适的算法来解决？

================

我在描述这个问题时做得很糟糕。让我再试一次：

我只有30分钟的时间来练习音乐。在这30分钟的时间里，我可以练习七首不同的歌曲。对于这七首歌中的每一首，我可以练习0，5，10，..，25，30分钟，但所有歌曲的总练习时间必须是30分钟。我有一些效用函数，可以对不同的可能练习计划进行评分。

Answer 1

编辑:正如Gassa指出的那样，在这里，顺序似乎并不重要。所以如果我现在理解这个问题，你想要itertools.combinations_with_replacement([1,2,3,4,5,6,7], r=6)

的老答案：

您正在寻找的是长度为6的1,2,3,4,5,6,7的所有排列(带有替换)。总而言之，应该有7^6=117649。使用this answer中描述的方法

import itertools
x = [1,2,3,4,5,6,7]
print len([p for p in itertools.product(x, repeat=6)])
# prints 117649

这为您提供了所有可能的日程安排-它们的格式与您所描述的格式不同(即您需要将"123123“转换为”歌曲1的10分钟，歌曲2的10分钟，歌曲3的10分钟“)，但转换速度很快。