动态规划：许多方式来获得至少N冒泡排序互换？

Question

让我们说我有针对其总体排序存在元件的阵列。冒泡排序距离是，它会采取对数组进行排序，如果我用冒泡排序交换次数。什么是有效的（可能会涉及动态编程）的方法来计算，将具有小于或等于某个预定数量？

冒泡排序距离该阵列的可能的排列的数量

如果它简化了问题，则可以假定该阵列的所有元素是唯一的（没有任何联系）。

Answer 1

确定，这里是一个解决方案。让我们假设数组的所有元素都是不同的，而且，不失一般性，我们可以假设它们是{1，...，N}。 （我们总是可以重新标记的元素，使这种情况下，并没有被影响。）

首先，我们可以观察到由冒泡排序进行互换的数量的的倒位在置换一个[1..N]的数量：这样的对的数量（I，J）我置于一个[J]。 （这不是太硬，以证明。）

因此，我们要的排列数{1，...，N}有超过k倒置。令c（N，K）表示这个号码。 {1，...，N}中的任意排列可以被认为是服用的排列{1，...，N-1}和插入{N}到它的地方。如果您在位置插入我，它创建完全相同N-1新的倒置。所以老置换必须有最多的k（N-1）倒置。这给出：

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 2 。）

---

<强>更新：上述需要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)

---

更新程序：（我写了一个懒memoised版本，你可以把它稍微更有效的通过使自下而上，用动态编程通常的方式）

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

有一个在用于编辑距离的瓦格纳 - 费希尔算法。你可能会朝一个方向：构建至少互换的表，它应该N×N在你的问题，你thatlets修建从左上角到右下角的表用一个不变的关系。