统一选择将物品分布放入垃圾箱中

想象一下你有n物品和m垃圾箱。所有物品都是相同的，但箱子是不同的。随机选择一批物品放入垃圾箱的最快算法是什么？

例如 - 想象一下104是将 5 件物品放入 3 个箱子中。将 5 件物品放入 3 个箱子中，有 21 种可能的放置方式：

005  014  023
032  041  050
104  113  122
131  140  203
212  221  230
302  311  320
401  410  500

对于大量物品和垃圾箱，我应该如何选择放置位置n项目进入m使每个可能的放置都有相同的发生机会？对于给定的n and m选择将会进行很多次。

这是针对两种情况的两种算法。

你有足够的可用内存，你会做很多展示位置。在这种情况下，您可以使用您的记忆来预先计算并存储您的所有可能的位置n项目进入m垃圾箱。如果我们让C(n, r)是以下组合的数量r物品取自n项目，不重复且不考虑顺序，则可能的放置数量为C(m+n-1, m-1)。 （该公式在组合数学中非常标准，并使用星条法 https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)#Theorem_two）。在你的例子中，那就是

C(5+3-1, 3-1) = C(7, 2) = 7!/2!/(7-2)! = 7/1*6/2 = 21

（如果 StackOverflow 中提供了 MathJax，我可以使用标准数学符号使其看起来更加漂亮。）在程序的设置中，可以通过一个小型递归例程使用以下想法生成这些位置：placek items (0 <= k <= n）放入第一个垃圾箱，然后将剩余的n-k项目进入剩余m-1垃圾箱。然后每次您想要随机放置时，请选择 1 到 1 之间的随机数C(m+n-1, m-1)并用它作为选择位置的索引。每次额外放置的时间成本只是一次随机数计算和一次数组访问。没有比这更好的了。

您的可用内存很少，您将进行一个或几个放置。然后，您可以使用计算多个组合系数的迭代例程来选择随机放置。

首先，计算一下你的可能的放置数量n项目进入m bins, C(m+n-1, m-1)，并选择一个随机数r从 1 到该组合数。让k是要放入第一个垃圾箱的物品数量。届时将会有n-k剩余项目在m-1bins 的数量为C(m+n-k-2, m-2)。现在循环k开始于0。如果这算的话k=0超过或等于r，我们决定设置k=0第一个垃圾箱中的物品。如果没有，增加k减一并减少r通过该组合计数，并为新的组合找到新的组合计数k。如果该计数超过或等于r，我们决定设置k第一个垃圾箱中的物品。如果没有，增加k通过一...你就明白了。当我们选择了一个特定的值k我们替换n with n-k, m with m-1, leave r就像现在一样，然后移动到下一个垃圾箱。

这个的计数是n迭代项目和m通过 bin 进行迭代，对于m+n组合系数的迭代和计算。唯一的内存使用是一些简单的变量和最终的放置m垃圾箱。您需要一个好的组合系数计算器例程。

(稍后添加：我已经完整地编写了这个例程，并找到了一种更好的方法来计算所涉及的概率，而无需找到组合的数量。这样减少了计算时间，完全实现了顺序m+n为了例行公事。这可以减少到订单m如果我能找到一个好的函数来直接找到一个给出一定概率的值，但我找不到这样的函数。如果您愿意获得近乎均匀的展示位置分布而不是完全均匀的分布，我可以找到近似值。）

让我知道如果您想要一些 Python 代码来演示任一例程，但首先要澄清您所处的情况并展示您自己的更多努力。