算法跟踪大量洗牌

Question

假设一个应用程序需要高效地存储大量洗牌后的牌组。是否存在一个恒定空间、恒定时间的算法，使得:

 index = draw_from_shuffled(element_count, number_of_draws_made, random_seed)

返回的值是下一张要从有序集合中抽取的卡片的索引。另外，索引不会重复，即:同一张牌不会抽两次。存储大量不同洗牌的牌组的需求将被一个随机数所取代，该随机数提供一种初始化向量，可以在其中对那组牌进行排序。存储 n 个洗牌后的牌组，需要存储 n 个整数值。

那么这样的算法存在吗？没有恒定时间的一种方法是使用 bloom filter跟踪已经绘制的卡片。数据要求将是恒定的，但最坏情况下的算法复杂度是 n!，这是不可取的。

Answer 1

保留一个包含 52 个整数的数组，其中每一项都是所有牌组中相应牌的总数(索引 1 表示 1 张红桃，对于 1000 副牌，该项目最初为 1000)。在绘制函数中:

1. 选择一个介于 0 和 1 之间的随机值 R。

2. 将 T 设为 0

3. 对于数组中的每一项:

   3-a。让 T = T + item/totalItems

   3-b。如果T>=R递减item，递减totalItems，返回item index

   3-c。转到3

假定牌组数量为整数，该算法具有恒定的空间和恒定的运行时复杂度。也许更准确地说，空间复杂度是 O(logD)。