동적 프로그래밍:최소한 N개의 버블 정렬 교환을 얻는 방법의 수는 무엇입니까?

Question

전체 순서가 존재하는 요소 배열이 있다고 가정해 보겠습니다.버블 정렬 거리는 버블 정렬을 사용하는 경우 배열을 정렬하는 데 필요한 스왑 수입니다.버블 정렬 거리가 미리 지정된 숫자보다 작거나 같은 이 배열의 가능한 순열 수를 계산하는 효율적인(동적 프로그래밍이 포함될 수 있음) 방법은 무엇입니까?

문제를 단순화하면 배열의 모든 요소가 고유하다고(연결되지 않음) 가정할 수 있습니다.

Answer 1

좋습니다. 해결책이 있습니다.배열의 모든 요소가 서로 다르다고 가정하고, 더 나아가 일반성을 잃지 않고 {1,...,n}이라고 가정할 수 있습니다.(우리는 항상 요소의 레이블을 다시 지정하여 아무 것도 영향을 받지 않도록 할 수 있습니다.)

먼저, 버블 정렬에 의해 수행된 교환 횟수는 다음과 같다는 것을 알 수 있습니다. 반전 순열 a[1..n]에서:i<j이지만 a[i]>a[j]인 쌍 (i,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)가 걸립니다. 따라서 O(n^4)까지 — c(n,k)를 계산하는 데 시간이 걸립니다. nk c(n,k) 각각을 계산하는 데 O(n) 시간이 걸리기 때문입니다. 이전 것들을 감안할 때.반복을 더 짧게 만들어 n배로 개선할 수 있으므로 각 c(n,k)는 이전의 경우 O(1) 시간에 계산될 수 있습니다.k-n+i에 대해 j를 쓰면 다음과 같습니다.

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)

Answer 2

살펴보십시오 Wagner-Fisher 알고리즘 편집 거리. 당신은 아마 같은 방향으로 향하고있을 것입니다 : 왼쪽에서 맨 아래로 오른쪽으로 테이블을 만드는 불변의 관계를 사용하여 문제에서 n × n이어야하는 최소 스왑 테이블을 구성하십시오.