Problem A - Minimum Swap

Diberikan kurang dari 27 huruf yang berisikan alphabet 'a' sampai 'z' secara acak dan unik (tidak berulang) dalam satu baris. Anda harus menukar dua posisi dari huruf di baris tersebut sehingga semua huruf menjadi terurut menaik. Berapa jumlah minimum pertukaran yang harus anda lakukan?

Perlu diketahui bahwa suatu permutasi kalau kita ikuti jejaknya, dia akan membentuk suatu cycle.

Contoh:

Ini adalah salah satu permutasi dari 10 angka dari 0..9:

8 2 9 5 4 6 3 1 0 7

Anda dapat membayangkan permutasi ini disimpan dalam array:

index: 0 1 2 3 4 5 6 7 8 9
array: 8 2 9 5 4 6 3 1 0 7

Dari sini anda bisa melihat ada 4 cycles. Suatu cycle terbentuk dari 
hubungan antara index dengan isi dari array tersebut yang menunjuk ke 
index lain dan seterusnya sampai kembali ke index awal.

0 -> 8 (-> 0)
1 -> 2 -> 9 -> 7 (-> 1)
3 -> 5 -> 6 (-> 3)
4 (-> 4)

Untuk setiap cycle dengan length C, anda hanya perlu C-1 swap untuk membenarkannya.
Jadi dalam contoh diatas, ke-empat cycle memiliki length:

0-8         // cycle length = 2
1-2-9-7     // cycle length = 4
3-5-6       // cycle length = 3
4           // cycle length = 1

Total minimum swap yang dibutuhkan adalah: 1 + 3 + 2 + 0 = 6 swaps

Untuk problem Minimum Swap ini, anda dipersulit sedikit dengan cara mengubah angka 0..N-1 diatas menjadi alphabet 'a' sampai 'z' dan ada alphabet yang tidak dipakai (lompat-lompat). Contohnya ada input seperti: "thznlqjgfs" dimana sebenarnya input ini bisa di-translate menjadi percis contoh diatas dan jawabannya adalah 6. Dibawah saya sertakan kode konversi alphabet menjadi permutasi array 0..N-1 untuk memudahkan pencarian cycle.

Ada cara kedua yang lebih mudah, yaitu anda hanya tinggal menghitung berapa banyak swap yang terjadi kalau anda melakukan selection-sort algorithm terhadap input tersebut. Jumlah swap untuk selection sort selalu minimum kalau element yang di-sort adalah unik (tidak ada duplikat). Karena ke-unik-an-nya ini, maka hanya ada satu kemungkinan swap yaitu swap element yang berada di posisi yang salah dengan element yang menempati posisi tersebut. Itulah yang dilakukan selection sort:

Dari kiri ke kanan menukarkan element i (kalau element i tidak pada tempatnya) dengan element yang seharusnya ada disana.

Apakah ada yang menemukan cara lain selain dua cara diatas?

#include <stdio.h>

int m[26], a[26];
char s[27];

int cycle(int i){
    if (a[i]!=i){
        int j = a[i];
        a[i] = i;
        if (a[j]!=j) return 1 + cycle(j);
    }
    return 1;
}

int main(){
    while (gets(s)){
        int i,j=0,res=0;
        for (i=0; i<26; i++) m[i] = 0;
        for (i=0; s[i]; i++) m[s[i]-'a'] = 1;
        for (i=0; i<26; i++) if (m[i]) m[i] = j++;   // mapping alphabet ke 0..N-1
        for (i=0; s[i]; i++) a[i] = m[s[i]-'a'];     // convert alphabet 'a'..'z' di s menjadi angka 0..N-1 di a
        for (i=0; s[i]; i++) res += cycle(i)-1;      // jumlah swap minimum adalah total semua individual cycleLength - 1
        printf("%d\n",res);
    }
}

#include <stdio.h>

char s[27];

int main(){
    while (gets(s)){
        int i,res=0;
        for (i=0; s[i]; i++){
            int j,k=i;
            for (j=i+1; s[j]; j++)
                if (s[j]<s[k]) k = j;
            if (k!=i){
                char t = s[i];
                s[i] = s[k];
                s[k] = t;
                res++;
            }
        }
        printf("%d\n",res);
    }
}

Lihat problem lain:

1. Minimum Swap
2. GCD!
3. Playing With Domino
4. Email from the Professor
5. Panda Number
6. Jakarta Traffic Jam
7. Sultan's Land
8. Tree Median