Хорошо, вот решение. Предположим, что все элементы массива различны, и далее, без потери общности, мы можем предположить, что они равны {1, ..., n}. (Мы всегда можем пометить элементы так, чтобы это было так, и ничто не повлияло.)
Во-первых, мы можем заметить, что число перестановок, выполненных с помощью пузырьковой сортировки, представляет собой число инверсий в перестановке a [1..n]: количество пар (i, j), таких, что я 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 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)
Обновленная программа: (я написал ленивую запоминающуюся версию; вы можете сделать ее немного более эффективной, сделав ее снизу вверх, обычным способом динамического программирования.)
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)