python - 泡泡洗牌 - 加权洗牌

Question

可以设想对冒泡排序进行修改，其中“交换”以概率 p 随机发生。 ，而不是通过执行比较。结果可以称为“泡沫洗牌”。靠近前面的元素可能会保留在那里，但有机会移到列表的后面。
修改从互联网上窃取的冒泡排序，您可以想出以下内容:

import random

def bubble_shuffle(arr, p):
    arr = copy.copy(arr)
    n = len(arr) 
  
    # Traverse through all array elements 
    for i in range(n-1): 
    # range(n) also work but outer loop will repeat one time more than needed. 
  
        # Last i elements are already in place 
        for j in range(0, n-i-1): 
  
            # traverse the array from 0 to n-i-1 
            # Swap if random number [0, 1] is less than p
            if random.random() < p:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

这个算法是 n 平方阶的……但是一个元素出现在任何特定位置的概率应该是可以提前计算的，所以它不需要“n 平方”。
有没有更有效的方法可以采取？
我曾考虑从几何分布中采样并将其添加到原始索引中(​​加上 (len(n)-i-1)/len(n) 以打破平局)，但这并没有给出相同的动态。

Answer 1

我同意 btilly 和其他人的看法，即相关性使这件事变得非常困难，如果不是不可能的话。
关于你的方法，单次通过的运动确实是几何分布的。然而，对于许多遍，中心极限定理开始发挥作用。忽略边界效应，在单遍中，元素向左移动一次的概率为 p。 ，否则(概率为 (1-p))向右移动几何次数，成功概率为 1-p .该分布的均值为零。第一种可能性贡献p (-1)^2 = p到方差。第二个投稿(1-p) sum_{i>=0} p^i (1-p) i^2 ，Wolfram Alpha 将其计算为 (1+p) p / (1-p) .
令此方差为 v = p + (1+p) p / (1-p) ，我们可以想象t之后元素的delta位置通过正态分布，均值为零和标准差sqrt(t v) .我们的下一个近似值是从离散时间切换到连续时间，并为每个元素提取一个正常样本 x并假设 delta 位置平滑变化为 sqrt(t v) x .对于最初在位置 i 的元素，我们可以解方程i + sqrt(t v) x = n - t为 t来估计该元素何时被锁定。然后我们就按那些 t 排序下降。
这是一个实现此功能的简短 Python 程序。希望它足够接近。

import math
import random


def variance(p):
    return p + (1 + p) * p / (1 - p)


def solve_quadratic(b, c):
    assert c < 0
    return (math.sqrt(b ** 2 - 4 * c) - b) / 2


def bubble_shuffle(arr, p):
    n = len(arr)
    s = math.sqrt(variance(p))
    return [
        arr[i]
        for i in sorted(
            range(n),
            key=lambda i: solve_quadratic(random.gauss(0, s), i - n),
            reverse=True,
        )
    ]


if __name__ == "__main__":
    print(bubble_shuffle(range(100), 0.5))