algorithm 정렬 시퀀스를 주문하기위한 최소한의 스왑 수 계산




서열 정렬 원리 (5)

정수 계열을 동일한 수로 정렬하는 작업을하고 있습니다 (일반성을 잃지 않고 시퀀스가 1,2,...,n 의 순열이라고 가정 해 봅시다) 1,2,...,n ). 나는 요소의 위치에 관계없이 요소를 직접 교환하는 것에 대해 생각하고 있었다. 즉, 최소한의 스왑 수 (다음은 실현 가능한 솔루션 일 수 있음)로 스왑은 두 요소에 대해 유효합니다.

두 요소 중 하나 또는 둘 모두가 올바른 위치로 교체되어야하는 제약 조건으로 두 요소를 서로 바꿉니다. 모든 요소가 올바른 위치에 놓일 때까지

그러나 위의 솔루션이 최적인지 수학적으로 증명할 방법을 모르겠습니다. 누구든지 도울 수 있니?

고맙습니다.


스위프트 4 버전 :

func minimumSwaps(arr: [Int]) -> Int {

      struct Pair {
         let index: Int
         let value: Int
      }

      var positions = arr.enumerated().map { Pair(index: $0, value: $1) }
      positions.sort { $0.value < $1.value }
      var indexes = positions.map { $0.index }

      var swaps = 0
      for i in 0 ..< indexes.count {
         var val = indexes[i]
         if val < 0 {
            continue // Already visited.
         }
         while val != i {
            let new_val = indexes[val]
            indexes[val] = -1
            val = new_val
            swaps += 1
         }
         indexes[i] = -1
      }
      return swaps
}

참조 용으로 여기에 배열을 정렬하는 데 필요한 최소 스왑 수를 생성하기 위해 작성한 알고리즘이 있습니다. @Andrew Mao의 설명에 따라주기를 찾습니다.

/**
 * Finds the minimum number of swaps to sort given array in increasing order.
 * @param ar array of <strong>non-negative distinct</strong> integers. 
 *           input array will be overwritten during the call!
 * @return min no of swaps
 */
public int findMinSwapsToSort(int[] ar) {
    int n = ar.length;
    Map<Integer, Integer> m = new HashMap<>();
    for (int i = 0; i < n; i++) {
        m.put(ar[i], i);
    }
    Arrays.sort(ar);
    for (int i = 0; i < n; i++) {
        ar[i] = m.get(ar[i]);
    }
    m = null;
    int swaps = 0;
    for (int i = 0; i < n; i++) {
        int val = ar[i];
        if (val < 0) continue;
        while (val != i) {
            int new_val = ar[val];
            ar[val] = -1;
            val = new_val;
            swaps++;
        }
        ar[i] = -1;
    }
    return swaps;
}

@bekce에 의해 훌륭하게 해결 된 솔루션. C #을 사용하는 경우 수정 된 배열 ar 을 설정하는 초기 코드는 간결하게 다음과 같이 표현할 수 있습니다.

var origIndexes = Enumerable.Range(0, n).ToArray();
Array.Sort(ar, origIndexes);

나머지 코드에서는 ar 대신 origIndexes 를 사용하십시오.


나는 이것을 그래프 이론으로 증명할 수 있었다. 그 태그를 추가하고 싶을 수도 있습니다 :)

n 개의 꼭지점이있는 그래프를 만듭니다. 위치 i 의 요소가 올바른 순서로 j 위치에있을 필요가있는 경우, 노드 n_i 로부터 n_j 까지의 엣지를 작성합니다. 이제 교차없는 여러 사이클로 구성된 그래프가 생깁니다. 그래프를 올바르게 정렬하는 데 필요한 스왑의 최소 개수는

M = sum (c in cycles) size(c) - 1

잠시 시간을내어 두 가지 항목이 순환하면 하나의 스왑이 처리 할 수 ​​있습니다. 3 개의 아이템이 한 싸이클에 있다면, 한 쌍을 바꿔 놓고 2 번 싸이클을 남긴다. n 아이템이 싸이클이면, n-1 스왑이 필요하다. (이웃과 직접 교환하지 않아도 항상 마찬가지입니다.)

그렇다면 이제 알고리즘이 왜 최적인지를 알 수 있습니다. 스왑을 수행하고 적어도 하나의 항목이 올바른 위치에 있으면 M 의 값을 1 씩 줄입니다. 길이가 n 인주기의 경우 요소를 해당 이웃이 차지하는 올바른 지점으로 교체하는 것을 고려하십시오. 이제 올바르게 정렬 된 요소와 길이 n-1 의주기가 있습니다.

M 은 스왑의 최소 수이기 때문에 알고리즘은 항상 스왑마다 M 을 1 씩 줄이므로 최적이어야합니다.


이것은 C ++에서 (1,2,3,4,5,.......n-2,n-1,n) 시퀀스의 순열을 정렬하는 최소 스왑 수를 찾는 샘플 코드입니다.

#include<bits/stdc++.h>
using namespace std;


int main()
{
    int n,i,j,k,num = 0;
    cin >> n;
    int arr[n+1];
    for(i = 1;i <= n;++i)cin >> arr[i];
    for(i = 1;i <= n;++i)
    {
        if(i != arr[i])// condition to check if an element is in a cycle r nt
        {
            j = arr[i];
            arr[i] = 0;
            while(j != 0)// Here i am traversing a cycle as mentioned in 
            {             // first answer
                k = arr[j];
                arr[j] = j;
                j = k;
                num++;// reducing cycle by one node each time
            }
            num--;
        }
    }
    for(i = 1;i <= n;++i)cout << arr[i] << " ";cout << endl;
    cout << num << endl;
    return 0;
}




graph-theory