如何以等概率以N种方式排列k个项目
How to arrange k items in N ways with equal probability
我有 7 个项目，k1-k7，我想以 30 种不同的方式排列它们，每个项目以相同的概率出现在每个位置。
k1, k2, k3, k4, k5, k6, k7
k1, k4, k5, k3, k7, k6, k2
.
k6, k2, k7, k1, k5, k4, k3
我不明白实现这个的方法是什么。请让我知道哪种算法适用于此。
我的第一次尝试是从列表中取出一个随机元素，然后从未选择元素的子集中取出一个随机元素，依此类推。对于第二个子集做同样的事情，完成后，检查它是否等于第一个子集。由于良好随机函数的均匀分布，它应该给你相等的概率
你不能，至少不能像描述中说的那样。如果 k_1 出现在每个位置的概率相同，那么它出现在位置 1 的组合数将等于它出现在其他每个位置的组合数。但这意味着组合的数量必须是 7 的倍数，而 30 不是。
如果你在绘制 30 个组合时只关心概率，那么按照 Brueni 的建议，随机选择序列是可行的方法。然而这与有30种组合无关，所以我怀疑这是你想要的？
如果我对你的理解正确，那么这些想法应该对你有用：
有 7! = 5040 种可能的元素排列方式。
在这些 5040 个独特序列中，有 6! = 720 个在第一个位置有 k1 个，720 个在第一个位置有 k2 个，... , 720 在最后一个位置有 k1, ... 等等。
所以，如果你从这5040个序列中随机抽取30个，我想结果应该符合你的要求。
怎么画呢？好吧，这取决于您使用的编程语言。在 C++ 中有 next_permutation. In python there is itertools.permutations。这些函数将按字典顺序遍历所有 7! 可能的排列。其他语言可能提供类似的工具。
然后，您可以在[0, ..., 5040[中随机生成一个数字n，并在初始范围内调用next_permutation n次（或者，在python , 将迭代器前进 n 次）。重复 30 次。
但是请注意，对于更大的数字，这很快就会变得非常低效，不确定您对效率的需求。
更新
我越想我的解决方案，我就越意识到如何绘制它们？可以更好地回答：
你只需要 uniform shuffle algorithm. This will by definition uniformly generate one of the 7! permutations which is exactly what my original answer does, but it will be much more efficient and much simpler to code as most languages provide such a shuffle algorithm (e.g. C++).
我会保留原来的答案，因为它可以帮助我（以及希望其他人）理解为什么统一洗牌是这里的正确解决方案。
我有 7 个项目，k1-k7，我想以 30 种不同的方式排列它们，每个项目以相同的概率出现在每个位置。
k1, k2, k3, k4, k5, k6, k7
k1, k4, k5, k3, k7, k6, k2
.
k6, k2, k7, k1, k5, k4, k3
我不明白实现这个的方法是什么。请让我知道哪种算法适用于此。
我的第一次尝试是从列表中取出一个随机元素，然后从未选择元素的子集中取出一个随机元素，依此类推。对于第二个子集做同样的事情，完成后，检查它是否等于第一个子集。由于良好随机函数的均匀分布，它应该给你相等的概率
你不能，至少不能像描述中说的那样。如果 k_1 出现在每个位置的概率相同，那么它出现在位置 1 的组合数将等于它出现在其他每个位置的组合数。但这意味着组合的数量必须是 7 的倍数，而 30 不是。
如果你在绘制 30 个组合时只关心概率，那么按照 Brueni 的建议，随机选择序列是可行的方法。然而这与有30种组合无关，所以我怀疑这是你想要的？
如果我对你的理解正确，那么这些想法应该对你有用：
有 7! = 5040 种可能的元素排列方式。
在这些 5040 个独特序列中，有 6! = 720 个在第一个位置有 k1 个，720 个在第一个位置有 k2 个，... , 720 在最后一个位置有 k1, ... 等等。
所以，如果你从这5040个序列中随机抽取30个，我想结果应该符合你的要求。
怎么画呢？好吧，这取决于您使用的编程语言。在 C++ 中有 next_permutation. In python there is itertools.permutations。这些函数将按字典顺序遍历所有 7! 可能的排列。其他语言可能提供类似的工具。
然后，您可以在[0, ..., 5040[中随机生成一个数字n，并在初始范围内调用next_permutation n次（或者，在python , 将迭代器前进 n 次）。重复 30 次。
但是请注意，对于更大的数字，这很快就会变得非常低效，不确定您对效率的需求。
更新
我越想我的解决方案，我就越意识到如何绘制它们？可以更好地回答：
你只需要 uniform shuffle algorithm. This will by definition uniformly generate one of the 7! permutations which is exactly what my original answer does, but it will be much more efficient and much simpler to code as most languages provide such a shuffle algorithm (e.g. C++).
我会保留原来的答案，因为它可以帮助我（以及希望其他人）理解为什么统一洗牌是这里的正确解决方案。