我有一个装有 100 个土豆的袋子。我需要将土豆分成 N 个桶。在每个桶中，我必须有 15 到 60 个土豆。
显然，我需要一个逐步的解决方案来将它变成代码。
到目前为止我最好的方法：
最小桶数：100/60 = 1 (40) => 向上取整 => 2
最大桶数：100/15 = 6 (10) => 向下取整 => 6
因此，您可以拥有最少 2 个和最多 6 个存储桶。现在我们选择一个随机数（因为我只需要一个解决方案，而不是全部）。
让我们选 3个。
每桶土豆：100/3 = 33 (1)
桶：33、33、34。
现在这是棘手的部分。虽然这是对原始问题的解决方案，但它对我不起作用，因为我需要数字比这更随机。在问题中，条件是 15-60，但在这里我们只得到 33-34，这对于我需要的来说太统一了。
这里的解决方案之一可能是开始从每个桶中添加和减去数字。可能要进行 10 次左右的迭代，但我认为必须有更好的方法来做到这一点。
有任何想法吗？
首先，分配所需的最少数量。在您的示例中，将 15 个放入每个存储桶中。如果您有 3 个桶，您将平均将 45 放入 3。剩余（R）：55。每个桶（C1，C2，C3）的剩余容量：45。
选择一个数字 k（参见关于如何选择 k 的脚注）。如果它大于 R，则将其设置为 R (k=min(k,R) )。随机挑选一个桶。如果 Ci 小于，则 k 将 k 设置为 Ci ( k=min(k,Ci) )。现在将 k 个土豆放入桶 i。更新 R 和 Ci (R=Rk, Ci=Ci-k)。重复此操作，直到所有土豆都吃完（R=0）。
脚注：选择 k
您可以设置 k=1 或从任何适当的分布中选择 k（例如：从 1 到 10 随机选择 k ）。
代码
import random
def distPotato(R, N, minP, maxP):
C = [maxP-minP for i in range(N)]
V = [minP for i in range(N)]
R-=sum(V)
while(R>0):
k = random.choice(range(10)) + 1
i = random.choice(range(N))
k = min(k,R)
k = min(k, C[i])
C[i]-=k
R-=k
V[i]+=k
return V
distPotato(100,3,15,60)
我想象在肉店里有一段牛肉，屠夫被要求在尽可能短的时间内把它切成 N 块随机大小。
他的第一个动作可能是随意敲击肉，确保在他进行 N-1 次切割之前，不要将其切得太靠近他之前的切片或边缘。
出于您的目的，这块牛肉可以是一排土豆。
所以要把它翻译成伪代码：
initiate a list of chosen potatoes to empty
while you have chosen less than N-1 potatos
pick a potato
if the potato is less than 15 potatoes away from a side
continue
if the potato is less than 15 potatoes away from a chosen potato
continue
add this potato to the chosen list
sort the chosen list
split the line of potatoes using the chosen potatoes as delimeters
我建议只是在桶中随机装满 15 到 60 个土豆，直到剩下的土豆少于 15 个。然后拿起你装满的最后一个桶，试着把剩下的土豆放进那个桶里。如果低于60，那就太好了！如果超过 60，则将桶分成两半。
所以假设你这样做了几次，你最终得到了 74 个土豆。你现在用一个随机数的土豆装满一个桶。假设它是 60 个。您现在还剩下 14 个土豆，对于另一个桶来说太少了，但对于您的最后一个桶来说太多了。很简单，倒出前一个桶（74 个土豆，再次），然后做两个桶，每个桶 37 个。
问题是你的最后两个桶不会像其他桶一样随机（或者至少不是“随机”，如果你愿意的话），但是因为你不能在一个桶里放少于 14 个土豆，所以你什么都没有可以做的。
首先，请注意，您可以稍微简化您的问题。而不是“每个桶需要包含 15 到 60 个土豆并且桶中的总数应该是 100”，您可以重述为“我需要 0 到 45 (60 - 15) 之间的 n 个数字，这样这些数字的总和为 100 - NX 15"。换句话说，用 15 个土豆填满你所有的桶，现在你正试图决定如何使用剩余的土豆来填满桶中剩余的空间。
假设你有 n 个桶要装，还有 p 个土豆。生成一个介于 0 到 45 之间的随机数 r，你现在剩下 p - r 个土豆。你现在能填满剩下的 (n-1) 个桶吗？
您可以将其写为递归解决方案：对于每个连续的桶，生成一个随机数的土豆，直到该数字不会阻止您在下一步找到解决方案。
下面是一个非常粗略的 F# 实现，显然可以对其进行改进/优化，但说明了算法的要点。allocation 是一个 int 列表，其中包含已分配给存储桶的数量，qty 是剩余要分配的土豆数量，buckets 是剩余存储桶的数量，min，max 是存储桶的容量。例如，有 100 个土豆和 3 个桶，您可以调用 solve 100 3 15 60。
结果分配应该是“尽可能随机”，即它应该以相同的概率产生任何可能的分配，但有一个警告：我假设桶的顺序无关紧要。鉴于该算法根据迄今为止分配的内容分配剩余的土豆，根据路径，列表的“头部”受到限制，并且分配可能会在第一个桶上分配更多。如果您想进行“真正的”随机分配，则需要在分配完成后对存储桶进行洗牌。
希望这可以帮助！
let rng = new System.Random()
let rec allocate allocation qty buckets min max =
match buckets with
| 0 -> allocation
| 1 -> qty :: allocation
| _ ->
let candidate = rng.Next(min, max + 1) // try a number in [min,max]
let rest = qty - candidate
if rest < (buckets - 1) * min // not enough left
then allocate allocation qty buckets min max // try again
else if rest > (buckets - 1) * max // too much left
then allocate allocation qty buckets min max // try again
else allocate (candidate :: allocation) rest (buckets - 1) min max
let solve qty buckets min max =
if min * buckets > qty then failwith "unfeasible"
if max * buckets < qty then failwith "unfeasible"
allocate [] qty buckets min max
ElKamina 的答案可能是正确的，但对于数学上的挑战，这里是另一种马铃薯分类算法。
from random import randint, choice
def random_distribution(num_potatoes, num_buckets, min_num_potatoes, max_num_potatoes):
"""
Distributes a set number of potatoes randomly across a number of buckets
such that each bucket has a number of potatoes within a certain range.
"""
# Cache the starting value
_num_potatoes = num_potatoes
# Create some buckets to put potatoes in, initial value 0
buckets = [0 for x in range(num_buckets)]
# Get a list of which buckets are not too empty or too full--
# All of them are valid choices at this point
indices = [i for (i, value) in enumerate(buckets)]
# Distribution loop-- continue until we run out of potatoes or the
# buckets are too full to keep adding to them.
while indices and num_potatoes and sum(buckets) <= (max_num_potatoes * num_buckets):
# Pick a random bucket from the list of eligible buckets
index = choice(indices)
# Add a potato to it
buckets[index] = buckets[index] + 1
num_potatoes = num_potatoes - 1
# Refresh the list of eligible buckets
indices = [i for (i, value) in enumerate(buckets) if (value < min_num_potatoes) or (value < max_num_potatoes)]
print('Of %(potatoes)i potatoes distributed across %(buckets)i buckets, each having at least %(min)i and at most %(max)i, our spread looks like %(spread)s (total bucketed: %(sum)i).' % {
'potatoes': _num_potatoes,
'buckets': num_buckets,
'min': min_num_potatoes,
'max': max_num_potatoes,
'spread': buckets,
'sum': sum(buckets)
})
return buckets
for x in range(10):
random_distribution(100, 3, 15, 60)
示例输出：
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [35, 37, 28] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [29, 36, 35] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [32, 27, 41] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [33, 33, 34] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [32, 32, 36] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [37, 28, 35] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [32, 27, 41] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [39, 27, 34] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [32, 30, 38] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [32, 30, 38] (total bucketed: 100).
在您给定的示例中，如果您想要更多的价值差异，您需要从更少的土豆开始或使用更多的桶。