Return 数组中的随机元素不包括子数组中的元素

Question

基本上，我需要这样的东西：

f(a[], b[]) = random element from a[] which is not in b[]

我的想法是这个：

while true:
   e = element_from_uniform(a[])
   if e not in b[]: return e

问题是，我希望这个函数更快，因为它会计算很多次（多个对象上的每一帧）。我知道，由于我们从均匀分布中进行选择，最终 a[] 中的一些元素会弹出 b[].

中不存在的元素

有什么想法吗？哦，如果有帮助的话，a[].length 总是 6 而 b[] 总是 a[] 和 b.length < a.length.

的某个子集

编辑：

我希望在不分配任何新内存的情况下完成此操作，仅使用指针。

Answer 1

您可以先创建$a \setminus b$。在 Python 中有例如函数 difference()。然后你可以从$s\setminus b$中随机选择一个元素...

Answer 2

为了更快的算法，您需要考虑实施的每个成本。

首先，如果 b 是 a 的子集，并且保持 b 排序，则可以使用二进制搜索 O = lg n 搜索任何元素。随机元素的拾取，如果您使用的是 x_{n+1} = x_{n} % M + b 形式的线性全等生成器，那么拾取随机元素是 O(1)

因此，通过这种方法，您可以返回 lg n，但保留 b 订购者在最坏的情况下可能会花费您 m lg m（其中 m = |b|) 使用归并排序或快速排序。

Return random element from array excluding elements from subarray