Cam*_*Cam 4 language-agnostic sorting random
是否存在一种算法,给定符号的有序列表{a1,a2,a3,...,ak},在O(n)时间内以随机顺序产生相同符号的新列表而没有偏差？"无偏差"是指任何符号s最终位于列表中某个位置p的概率为1/k.
假设可以在O(1)时间内生成1-k(包括1-k)的非偏置整数.还假设O(1)元素访问/变异是可能的,并且可以在O(k)时间内创建大小为k的新列表.
特别是,我会对'生成'算法感兴趣.也就是说,我会对具有O(1)初始开销的算法感兴趣,然后为列表中的每个插槽生成一个新元素,每个时隙花费O(1)时间.
如果所描述的问题不存在解决方案,我仍然想知道以下一种或多种方式(和/或必要时以其他方式)不符合我的约束的解决方案:
我应该补充一点,这个问题似乎与从1-k随机排序整数的问题相同,因为我们可以从1-k中排序整数列表,然后对于新列表中的每个整数i,我们可以生成符号ai.