动态规划：至少进行N次冒泡排序交换的方法数是多少？

Question

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

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

- dsimcha

---

问题的标题写着“至少 N 次冒泡排序交换”，而问题的正文却说“冒泡排序距离小于或等于某个预定的数字”——到底是哪一个？ - ShreevatsaR

这是一个合理的错误，但它并不太重要。它们只是同一个问题的不同形式。 - dsimcha

我在下面的回答中假设你的意思是“最多k个冒泡排序交换”。因此，n个元素的排列中至少有k个冒泡排序交换的数量为[n！-最多k-1个交换的排列数]。 - ShreevatsaR

Answer 1

好的，这里有一个解决方案。我们假设数组的所有元素都是不同的，并且进一步假设它们是 {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)

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

---

更新：上述方法需要O(n^2k)的时间来计算c(n,k)，因为每个nk c(n,k)在给定之前的c(n,k)时需要O(n)的时间来计算。我们可以通过缩短递归来提高n倍，以便每个c(n,k)在给定之前的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)

- ShreevatsaR

Answer 2

看一下Wagner-Fisher 算法，用于计算编辑距离。你可能朝着同样的方向前进：使用一个不变关系构建一个最小交换表，在你的问题中应该是 n×n 的，让你可以从左上角到右下角逐步构建出表。

- Charlie Martin

---

我不认为那是有用或相关的...虽然它与某些相似之处，但它对这里有何帮助呢？ - ShreevatsaR

我不同意。我也怀疑这可能有点像作业，所以我在暗示一个方向。 - Charlie Martin

这不是一个作业问题。我试图摆脱所有不必要的背景，只保留我卡住的部分，但实际上，这是为了计算 Kendall's tau 相关性的精确 P 值。 - dsimcha

好的，我在研究生阶段曾经被一个人创造了这些动态规划问题的方式所创伤（事实上是Wagner-Fisher算法中的Wagner）。尽管如此，我认为这就是你需要的模式。 - Charlie Martin

好的，我没有代码来展示解决方案，但考虑一下：交换恰好是一个删除和插入。因此，可以通过简化使用 WF。 - Charlie Martin