泡泡洗牌-加权洗牌

可以设想对冒泡排序进行修改，其中“交换”以概率随机发生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)打破平局），但这并没有给出相同的动态。