我有一个 30-60 范围内的随机整数，我使用 randint(30,60) 获得。假设它是 40。我想将这个数字分成 7 个随机整数。因此，例如 [5,5,5,5,5,5,10] 是一个有效的结果。但是有很多可能的解决方案，比如这个 [6,6,6,6,6,6,4] 或 [4,2,9,13,8,1 ,3] ... 我知道有很多解决方案，但我正在寻找一种快速的方法来解决它们。我并不是要获得每一个解决方案，而是寻找一种快速的方法来在短时间内迭代其中的许多解决方案。实现它的一种方法是随机选择一个数字(假设在 1-15 范围内)并将其保存到列表中，然后执行 while 循环直到总和正好是 40。我试过了，但效率不高全部。我认为选择像 [5,5,5,5,5,5,10] 这样的起始值并以像 "1st digit -2"这样的精确方式改变数字 和 3rd +2 产生 [3,5,7,5,5,5,10] 将是一个更快的解决方案。有谁知道该怎么做或有好的建议吗？谢谢。我更喜欢 python 3。
请您参考如下方法:
一组总和为 n 的整数称为 partition n；如果顺序很重要，那么它就称为组合。
这是一种生成随机组合的相当快速的方法。
import random
def random_partition(n, size):
seq = []
while size > 1:
x = random.randint(1, 1 + n - size)
seq.append(x)
n -= x
size -= 1
seq.append(n)
return seq
n = 40
for _ in range(20):
print(random_partition(n, 7))
典型输出
[26, 2, 8, 1, 1, 1, 1]
[30, 2, 1, 3, 1, 1, 2]
[26, 5, 3, 1, 2, 2, 1]
[2, 25, 9, 1, 1, 1, 1]
[28, 2, 2, 2, 1, 2, 3]
[23, 1, 9, 3, 2, 1, 1]
[3, 26, 1, 7, 1, 1, 1]
[25, 1, 7, 1, 2, 1, 3]
[10, 8, 11, 5, 3, 1, 2]
[19, 16, 1, 1, 1, 1, 1]
[12, 23, 1, 1, 1, 1, 1]
[1, 14, 15, 7, 1, 1, 1]
[29, 5, 1, 1, 2, 1, 1]
[25, 1, 3, 3, 1, 2, 5]
[10, 12, 10, 4, 1, 2, 1]
[13, 4, 6, 14, 1, 1, 1]
[31, 3, 1, 1, 1, 1, 2]
[16, 11, 9, 1, 1, 1, 1]
[3, 26, 5, 3, 1, 1, 1]
[31, 2, 1, 2, 2, 1, 1]
我们使用 1 + n - size 作为上限，因为其他 size - 1 数字至少为 1。
这是生成给定整数的所有分区的一种相当有效的方法。请注意，这些是有序的；如果您想从这些分区中生成随机组合，您可以使用 random.shuffle。
我们首先打印所有 16 个大小为 5 的分区，然后我们统计大小为 40 个大小为 7 的分区的数量 (= 2738)。
此代码源自 Jerome Kelleher 的算法.
def partitionR(num, size):
a = [0, num] + [0] * (num - 1)
size -= 1
k = 1
while k > 0:
x = a[k - 1] + 1
y = a[k] - 1
k -= 1
while x <= y and k < size:
a[k] = x
y -= x
k += 1
a[k] = x + y
if k == size:
yield a[:k + 1]
for u in partitionR(16, 5):
print(u)
print('- ' * 32)
print(sum(1 for _ in partitionR(40, 7)))
输出
[1, 1, 1, 1, 12]
[1, 1, 1, 2, 11]
[1, 1, 1, 3, 10]
[1, 1, 1, 4, 9]
[1, 1, 1, 5, 8]
[1, 1, 1, 6, 7]
[1, 1, 2, 2, 10]
[1, 1, 2, 3, 9]
[1, 1, 2, 4, 8]
[1, 1, 2, 5, 7]
[1, 1, 2, 6, 6]
[1, 1, 3, 3, 8]
[1, 1, 3, 4, 7]
[1, 1, 3, 5, 6]
[1, 1, 4, 4, 6]
[1, 1, 4, 5, 5]
[1, 2, 2, 2, 9]
[1, 2, 2, 3, 8]
[1, 2, 2, 4, 7]
[1, 2, 2, 5, 6]
[1, 2, 3, 3, 7]
[1, 2, 3, 4, 6]
[1, 2, 3, 5, 5]
[1, 2, 4, 4, 5]
[1, 3, 3, 3, 6]
[1, 3, 3, 4, 5]
[1, 3, 4, 4, 4]
[2, 2, 2, 2, 8]
[2, 2, 2, 3, 7]
[2, 2, 2, 4, 6]
[2, 2, 2, 5, 5]
[2, 2, 3, 3, 6]
[2, 2, 3, 4, 5]
[2, 2, 4, 4, 4]
[2, 3, 3, 3, 5]
[2, 3, 3, 4, 4]
[3, 3, 3, 3, 4]
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
2738
