algorithm - 动态规划：获得至少 N 次冒泡排序交换的方法有多少？

Question

假设我有一个元素数组，其中存在总排序。冒泡排序距离是在我使用冒泡排序时对数组进行排序所需的交换次数。什么是一种有效的（可能涉及动态编程）方法来计算该数组的可能排列的数量，其冒泡排序距离小于或等于某个预先指定的数字？

如果它简化了问题，您可以假设数组的所有元素都是唯一的（没有关系）。

Answer 1

好的，这是一个解决方案。让我们假设数组的所有元素都是不同的，并且进一步，不失一般性，我们可以假设它们是 {1,...,n}。（我们总是可以重新标记元素，这样就不会受到影响。）

首先，我们可以观察到冒泡排序执行的交换次数是排列 a[1..n] 中的反转次数：满足 i<j but a[i]> 的对 (i,j) 的数量一个[j]。（这并不难证明。）

所以我们想要 {1,...,n} 的排列数最多有 k 个反转。让 c(n,k) 表示这个数字。{1,...n} 的任何排列都可以被认为是采用 {1,...,n-1} 的排列并将 {n} 插入其中某处。如果将它插入到位置 i，它会创建恰好 ni 个新的反转。所以旧的排列最多只能有 k-(ni) 次反转。这给出了：

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)

（注意 k 最多为 n*(n-1)/2 < n ²。）

---

更新：上面需要 O(n^2k) - 所以最多 O(n^4) - 计算 c(n,k) 的时间，因为每个 nk c(n,k) 需要 O(n) 时间给定较早的计算。我们可以通过缩短递归来提高 n 倍，这样每个 c(n,k) 可以在给定较早的 O(1) 时间内计算出来。为 k-n+i 写 j 使得

c(n,k) = sum_{j=max(k-n+1,0) to k} c(n-1, j)

请注意，c(n,k) 和 c(n,k-1) 的大部分总和是相同的。具体来说，

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)

Answer 2

查看用于编辑距离的Wagner-Fisher 算法。您可能正朝着相同的方向前进：构建一个最少交换表，在您的问题中应该是 n×n，使用允许您从左上角到右下角构建表的不变关系。