时间戳

首页 > 解决方案 > 使用许多重复项对列表进行改组的有效算法或方法？

python - 使用许多重复项对列表进行改组的有效算法或方法？

问题描述

假设我有 5 个弹珠，3 个是红色的，2 个是蓝色的。相同颜色的弹珠从1到编号n，其中n是该颜色的弹珠的数量。

我需要的是洗牌列表的方法['red', 'red', 'red','blue', 'blue']，其中单个弹珠的排列无关紧要。

例如 ['red1', 'red2', 'red3','blue', 'blue']和 ['red2', 'red1', 'red3','blue', 'blue'] 只是一种解决方案。

因为我最初的问题有更多的一种颜色的弹珠，与其他问题相比，列表的正常洗牌会导致某些订单的偏差很大。

我的一个想法是：

  1. 从一个新的空列表开始，
  2. 生成 2 个随机整数（第一个整数选择颜色，第二个整数确定选择该颜色的弹珠数量）
  3. 将挑选的弹珠添加到新列表中
  4. 重复直到所有弹珠都用完

我想知道是否有更好的方法来解决这个问题，也许有更保证无偏见的结果。

编辑：一个小规模的场景将是 4 种不同的颜色，每种颜色有 2 到 5 个弹珠。现实情况是 20 差异。颜色，每种颜色有 5 到 50 个弹珠。

标签： pythonalgorithmlistshuffle

解决方案

如果您想要一个无偏的洗牌，那么您将您的算法与 Knuth 的（Fisher-Yate 的稍微改进的版本）洗牌进行比较

如果您要使用两阶段选择进行优化并希望它保持公平，您需要计算运行一、二、三相同颜色的概率，并比相应的交换次数更有效地执行此计算，然后将源中的副本数量复制到目标列表中。

我不会为性能而烦恼，因为对于 1000 个弹珠，您不太可能通过对交换进行数学运算来提高性能 - 您将不得不在每个阶段进行另一个列表迭代来计算概率，然后额外的工作将使其成为 O(N²) 而不是 O(N)。

推荐阅读