Obliczyć minimalną liczbę zamiany, aby zamówić sekwencję

Question

wcześniej pracowałem nad sortowaniem sekwencji całkowitych bez identycznych liczb (bez utraty ogólności, załóżmy, że sekwencja jest permutacją 1,2,...,n) w jej naturalnym porządku rosnącym (tj. 1,2,...,n) . Zastanawiam się, jak zamienić elementy (bez względu na pozycje elementów, innymi słowy, zamiana jest ważna dla dowolnych dwóch elementów) z minimalną liczbą zamian. Domyślam się, że jest to wykonalny algorytm:

Zamień dwa elementy z ograniczeniem, w którym jeden lub oba z nich powinny zostać zamienione na prawidłowe pozycje. Dopóki każdy element nie zostanie umieszczony we właściwym miejscu.

Ale nie wiem, jak matematycznie udowodnić, czy powyższy algorytm może prowadzić do optymalnego rozwiązania. Ktoś może pomóc?

Dziękuję bardzo.

Answer 1

Udało mi się to udowodnić za pomocą teorii grafów. Może chcieć dodać ten tag: :)

Utwórz wykres z wierzchołkami n. Utwórz krawędź od węzła n_i do n_j, jeśli element w pozycji i powinien znajdować się w pozycji j we właściwej kolejności. Będziesz teraz miał wykres składający się z kilku nie przecinających się cykli. I twierdzą, że minimalna liczba potrzebnych swapy na zamówienie wykres poprawnie jest

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

Poświęć chwilę, aby przekonać się, że ... jeśli dwa elementy są w cyklu, jedna zamiana może po prostu się nimi zająć. Jeśli trzy elementy znajdują się w jednym cyklu, możesz zamienić parę, aby umieścić ją we właściwym miejscu, a pozostało dwa cykle, itd. Jeśli pozycje n są w cyklu, potrzebujesz wymieniać n-1. (Jest to zawsze prawdziwe, nawet jeśli nie zamienisz się z bezpośrednimi sąsiadami).

Biorąc to pod uwagę, możesz teraz zobaczyć, dlaczego Twój algorytm jest optymalny. Jeśli wykonasz zamianę, a co najmniej jeden element znajdzie się we właściwej pozycji, zawsze zmniejszy on wartość o M o 1. Dla dowolnego cyklu o długości n, rozważ zamiana elementu na właściwe miejsce zajmowane przez jego sąsiada. Masz teraz poprawnie uporządkowany element i cykl o długości n-1.

Ponieważ M to minimalna liczba zamian, a Twój algorytm zawsze redukuje M o 1 dla każdej wymiany, musi być optymalny.

Answer 2

Dla twojego odniesienia, oto algorytm, który napisałem, aby wygenerować minimalną liczbę zamian potrzebnych do posortowania tablicy. Znajduje cykle opisane przez @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; 
} 

Answer 3

Ładnie wykonane rozwiązanie przez @bekce. W przypadku korzystania z C# kod początkowy utworzenia zmodyfikowanej tablicy ar może być zwięźle wyrażona jako:

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

następnie użyć origIndexes zamiast ar w pozostałej części kodu.

Answer 4

To jest przykładowy kod w C++, który znajdzie minimalną liczbę swapów posortować permutacji sekwencji (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; 
}