algorithm - 动态规划 : Number of ways to get at least N bubble sort swaps?

Question

假设我有一个存在总排序的元素数组。如果我使用冒泡排序，冒泡排序距离是对数组进行排序所需的交换次数。什么是一种有效的(可能涉及动态规划)方法来计算此数组的可能排列数，使冒泡排序距离小于或等于某个预先指定的数字？

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

Answer 1

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

首先，我们可以观察到冒泡排序执行的交换次数是排列a[1..n]中反转的次数:这样的对(i,j)的数目即 ia[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)

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

---

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

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)