Динамическое программирование: сколько способов получить по крайней мере N свопов пузырьковой сортировки?

Хорошо, вот решение. Предположим, что все элементы массива различны, и далее без ограничения общности можно считать, что это {1,...,n}. (Мы всегда можем переименовать элементы так, чтобы это было так, и ничего не пострадает.)

Во-первых, мы можем заметить, что количество перестановок, выполненных пузырьковой сортировкой, равно количеству инверсий в перестановке a[1..n]: количеству пар (i,j), таких что i‹ j, но a[i]›a[j]. (Это не так уж сложно доказать.)

Итак, нам нужно количество перестановок {1,...,n} с не более чем k инверсиями. Пусть 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) — то есть до O(n^4) — времени для вычисления c(n,k), поскольку каждый из nk c(n,k)' s требует 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)

Взгляните на алгоритм Вагнера-Фишера для редактирования расстояний. Вероятно, вы движетесь в том же направлении: создайте таблицу наименьших свопов, которая должна быть nn в вашей задаче, используя инвариантное отношение, которое позволяет вам строить таблицу от верхнего левого угла к нижнему правому.