假设我有一个元素数组,其中存在总排序。 冒泡排序距离是如果我使用冒泡排序来对数组进行排序所需的交换次数。 有什么有效的(可能涉及动态编程)方法来计算可能排列的数量,使其冒泡排序距离小于或等于某个预先指定的数字?
如果简化问题,您可以假设数组的所有元素都是唯一的(没有平局)。
如果简化问题,您可以假设数组的所有元素都是唯一的(没有平局)。
好的,这里有一个解决方案。我们假设数组的所有元素都是不同的,并且进一步假设它们是 {1,...,n},没有损失地,我们可以假设它们是 {1,...,n}。 (我们总是可以重新标记元素,使其成为这种情况,而不会影响任何东西。)
首先,我们可以观察到冒泡排序执行的交换次数是排列 a[1..n] 中的逆序对数:即对 (i,j) 的数量,其中 i<j 但 a[i]>a[j]。(这不太难证明。)
因此,我们希望知道具有至多 k 个逆序对的 {1,...,n} 的排列数。让 c(n,k) 表示这个数字。{1,...n} 的任何排列都可以被看作是将 {1,...,n-1} 的排列插入某个位置 {n}。如果您在位置 i 插入它,则会创建恰好 n-i 个新的逆序对。因此,旧排列必须最多有 k-(n-i) 个逆序对。这给出:
c(n,k) = sum_{i s.t. n-i≤k} c(n-1, k-(n-i))
= sum_{i=max(1,n-k) to n} c(n-1, k-n+i)
还有一个基本情况:
c(1,0) = 1 (or better, c(0,0)=1)
c(n,k) = sum_{j=max(k-n+1,0) to k} c(n-1, j)
When k≤n-1, c(n,k) = c(n,k-1) + c(n-1,k)
When k≥n, c(n,k) = c(n,k-1) + c(n-1,k) - c(n-1,k-n)
更新的程序:(我写了一个懒惰的记忆化版本;你可以通过使用自底向上的动态规划方法使其更加高效。)
ct = {(0,0): 1}
def c(n,k):
if k<0: return 0
k = min(k, n*(n-1)/2) #Or we could directly return n! if k>=n*(n-1)/2
if (n,k) in ct: return ct[(n,k)]
ct[(n,k)] = c(n,k-1) + c(n-1,k) - c(n-1,k-n)
return ct[(n,k)]
if __name__ == "__main__":
n = input("Size of array: ")
k = input("Bubble-sort distance at most: ")
print c(n,k)
看一下Wagner-Fisher 算法,用于计算编辑距离。你可能朝着同样的方向前进:使用一个不变关系构建一个最小交换表,在你的问题中应该是 n×n 的,让你可以从左上角到右下角逐步构建出表。