随机将元素放入N个桶中

Question

我有一袋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 次左右，但我认为一定有更好的方法来做到这一点。

有任何想法吗？

Answer 1

首先，分配所需的最少数量。在您的示例中，将 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)