Apakah mungkin untuk menemukan apakah ada urutan dalam waktu polinomial dalam masalah berikut?

Saya sudah memikirkan masalah berikut untuk sementara waktu, dan saya belum menemukan solusi polinomial untuk itu. Hanya sumber kasar. Saya sudah mencoba untuk mengurangi masalah NP-Complete ke dalamnya juga tanpa keberhasilan.

Inilah masalahnya :

Anda memiliki set yang diurutkan $\{(A_1, B_1), (A_2, B_2), \ldots, (A_n, B_n)\}$ dari pasangan bilangan bulat positif.

$(A_i, B_i) < (A_j, B_j) \Leftrightarrow A_i < A_j \lor (A_i = A_j \land B_i < B_j)$ $(A_i, B_i) = (A_j, B_j) \Leftrightarrow A_i = A_j \land B_i = B_j$

Operasi berikut dapat diterapkan untuk sepasang: Swap(pair). Ini menukar elemen pasangan, sehingga $(10, 50)$ akan menjadi $(50, 10)$

Ketika pasangan di set ditukar, set secara otomatis akan diurutkan lagi (pasangan bertukar tidak pada tempatnya dan itu akan dipindahkan ke tempatnya di set)

Masalahnya terdiri pada melihat apakah ada urutan yang, dimulai pada beberapa pasangan, menukar seluruh rangkaian, dengan kondisi berikut:

Setelah satu pasangan ditukar, pasangan berikutnya yang akan ditukar harus menjadi penerus atau pasangan predecesor di set.

Akan sangat bagus untuk menemukan solusi waktu polinomial untuk masalah ini, atau pengurangan masalah NP-Complete ke dalamnya.

Catatan:
Ini sudah menjadi masalah keputusan. Saya tidak ingin tahu urutan mana: hanya jika ada urutan.

Contoh bagaimana set akan diurutkan setelah bertukar pasangan

$\textbf{(6, 5)}$
$(1,2)$
$(3,4)$
$(7,8)$

Jika saya menukar pasangan pertama, itu menjadi: $(5,6)$ , dan setelah mengurutkan set (menempatkan pasangan yang diurutkan di posisi baru), kita memiliki:

$(1,2)$
$(3,4)$
$\textbf{(5,6)}$
$(7,8)$

Maka saya harus menukar salah satu (pendahulu) atau ( 7 , 8 ) (penerus), dan ulangi prosesnya sampai semua pasangan bertukar (jika memungkinkan).$(3,4)$$(7,8)$

Penting:
Anda tidak dapat menukar pasangan yang sudah ditukar.
Jika ada urutan operasi 'swap', maka semua pasangan harus diganti namanya menjadi sekali dan hanya sekali.

Contoh di mana tidak mungkin untuk menukar semua pasangan

( 1 , 4 ) ( 3 , 2 $(0, 0)$
$(1, 4)$
$(3, 2)$
$(5, 5)$

... Saya mencari beberapa pola untuk membuat pengurangan dari masalah NPC, tetapi tidak menemukan cara untuk mewakili "aliran" dengan "garpu" ...

Jadi (setelah beberapa pekerjaan) ini adalah algoritma polinomial ...

ALGORITMA

Daftar awal dapat dilihat sebagai larik " lubang " berurutan . Untuk setiap pasangan awal ( a j , b j ) , letakkan " elemen " b j pada nomor lubang a j . Setiap pasangan dapat dilihat sebagai tepi diarahkan dari posisi suatu j ke posisi b j . Sebuah langkah terdiri dalam memilih sebuah elemen b j pada posisi yang j dan pindah ke nya posisi tujuan b $N*2$$(a_j,b_j)$$b_j$$a_j$$a_j$$b_j$$b_j$$a_j$$b_j$(lubang tujuan menjadi pasak tidak bergerak ). Kami menghapus tepi, dan lanjutkan untuk memilih langkah selanjutnya yang akan dimulai dari salah satu dari dua unsur dicapai terdekat dari posisi b j (hanya lubang antara b j dan b k diperbolehkan). Kami harus menemukan urutan gerakan N berturut-turut.$b_k$$b_j$$b_j$$b_k$$N$

• Untuk masing-masing pertimbangkan b j (pada posisi larik a j ) sebagai elemen awal s t a r t .$(a_j,b_j)$$b_j$$a_j$$start$

  • Untuk masing-masing pertimbangkan a k sebagai elemen terakhir e n d (tepi dari posisi a k ke posisi b $(a_k,b_k), a_k \neq a_j$$a_k$$end$$a_k$$b_k$ akan menjadi ujung akhir).

    • menghasilkan urutan gerakan dari menggunakan kriteria berikut sampai Anda mencapai elemen e n d (dan solusi telah ditemukan), atau kondisi berhenti$start$$end$

Ketika Anda bergerak, Anda mematok pasak pada posisi dan array dibagi menjadi dua partisi L (kiri) dan R (kanan) dan satu-satunya cara untuk beralih dari L ke R (atau dari R ke L ) menggunakan tepi yang melompat di pasak. Set$b_j$$L$$R$$L$$R$$R$$L$

• = jumlah tepi dari kiri ke kanan (jangan hitung tepi akhir)$edgesLR$
• = jumlah tepi dari kanan ke kiri (jangan hitung tepi akhir)$edgesRL$
• = e d g e s L R - e d g e s R $flow$$edgesLR - edgesRL$

Kasus:

A) jika maka salah satu dari dua partisi akan menjadi tidak terjangkau, berhenti$| flow | > 1$

Sekarang anggaplah bahwa , yaitu e n d ∈ $end > b_j$$end \in R$

B) jika maka ada keunggulan tambahan dari kiri ke kanan, Anda harus pergi kiri (memilih elemen terdekat dari L ), jika tidak, anda tidak akan pernah mencapai e n $flow = 1$$L$$end$

C) jika maka ada tepi ekstra dari kanan ke kiri dan simpul apa pun yang Anda pilih, Anda tidak akan pernah mencapai e n $flow = -1$$end$ , berhenti

D) jika Anda harus pergi ke kanan (memilih elemen terdekat dari R ), jika tidak Anda akan neve jangkauan e n $flow = 0$$R$$end$

Jika ( e n d ∈ L ), B, C, D terbalik.$end < b_j$$end \in L$

CATATAN: saat bergerak ke kiri atau ke kanan, Anda harus mempertimbangkan sebagai pasak. Misalnya, jika Anda harus berbelok ke kanan, tetapi elemen terdekat pada R adalah e n d maka langkah tersebut tidak mungkin (dan Anda harus melanjutkan dengan pasangan lain ( s t a r t , e n d ) )$end$$R$$end$$(start,end)$

Terapkan pengubahan ulang yang sama di setiap gerakan.

KOMPLEKSITAS

Aliran pada setiap lubang dapat dihitung ulang dalam O (N) dan digunakan kembali pada setiap pemindaian.

Loop adalah:

for start = 1 to N
  for end = 1 to N
    for move = 1 to N
      make a move (fix a peg and update flows)
      check if another move can be done using flow     

Tidak ada pilihan yang dibuat selama perhitungan, sehingga kompleksitas algoritma adalah $O(N^3)$

KODE

Ini adalah implementasi algoritma Java yang berfungsi:

public class StrangeSort {
    static int PEG = 0xffffff, HOLE = 0x0;
    static int M = 0, N = 0, choices = 0, aux = 0, end;
    static int problem[][], moves[], edgeflow[], field[];    
    boolean is_hole(int x) { return x == HOLE; }
    boolean is_peg(int x) { return x == PEG; }
    boolean is_ele(int x) { return ! is_peg(x) && ! is_hole(x); };
    int []cp(int src[]) { // copy an array
        int res[] = new int[src.length];
        System.arraycopy(src, 0, res, 0, res.length);
        return res;
    }    
    /* find the first element on the left (dir=-1) right (dir=1) */
    int find(int pos, int dir, int nm) {
        pos += dir;
        while (pos >= 1 && pos <= M ) {
            int x = field[pos];
            if ( is_peg(x) || (pos == end && nm < N-1) ) return 0;
            if ( is_ele(x) ) return pos;
            pos += dir;
        }
        return 0;
    }
    void build_edges() {
        edgeflow = new int[M+1];
        for (int i = 1; i<=M; i++) {
            int start = i;
            int b = field[start];
            if (! is_ele(b)) continue;
            if (i == end) continue;
            int dir = (b > start)? 1 : -1;
            start += dir;
            while (start != b) { edgeflow[start] += dir; start += dir; }
        }
    }
    boolean rec_solve(int start, int nm) {
        boolean f;
        int j;
        int b = field[start];
        moves[nm++] = b;
        if (nm == N) return true;
        //System.out.println("Processing: " + start + "->" + field[start]);        
        field[start] = HOLE;
        field[b] = PEG;
        int dir = (b > start)? 1 : -1;
        int i = start + dir;
        while (i != b) { edgeflow[i] -= dir; i += dir; } // clear edge                
        int flow = edgeflow[b];
        if (Math.abs(flow) > 2) return false;
        if (end > b) {
            switch (flow) {
            case 1 :                    
                j = find(b,-1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            case -1 :
                return false;
            case 0 :          
                j = find(b,1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            }        
        } else {
            switch (flow) {
            case -1 :                    
                j = find(b,1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            case 1 :
                return false;
            case 0 :          
                j = find(b,-1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            }            
        }
        return false;
    }
    boolean solve(int demo[][]) {
        N = demo.length;
        for (int i = 0; i < N; i++)
            M = Math.max(M, Math.max(demo[i][0], demo[i][1]));
        moves = new int[N];
        edgeflow = new int[M+1];
        field = new int[M+1];
        problem = demo;        
        for (int i = 0; i < problem.length; i++) {
            int a = problem[i][0];
            int b = problem[i][1];
            if ( a < 1 || b < 1 || a > M || b > M || ! is_hole(field[a]) || ! is_hole(field[b])) {
                System.out.println("Bad input pair (" + a + "," + b + ")");
                return false;
            }
            field[a] = b;
        }
        for (int i = 1; i <= M; i++) {
            end = i;
            build_edges();
            if (!is_ele(field[i])) continue;
            for (int j = 1; j <= M; j++) {
                if (!is_ele(field[j])) continue;
                if (i==j) continue;
                int tmp_edgeflow[] = cp(edgeflow);
                int tmp_field[] = cp(field);
                choices = 0;
                //System.out.println("START: " + j + " " + " END: " + i);
                if (rec_solve(j, 0)) {
                    return true;
                }
                edgeflow = tmp_edgeflow;
                field = tmp_field;
            }
        }
        return false;
    }
    void init(int demo[][]) {

    }
    public static void main(String args[]) {
        /**** THE INPUT ********/        

        int demo[][] =  {{4,2},{5,7},{6,3},{10,12},{11,1},{13,8},{14,9}};

        /***********************/        
        String r = "";
        StrangeSort sorter = new StrangeSort();       
        if (sorter.solve(demo)) {
            for (int i = 0; i < N; i++) { // print it in clear text
                int b =  moves[i];
                for (int j = 0; j < demo.length; j++)
                    if (demo[j][1] == b)
                        r += ((i>0)? " -> " : "") + "(" + demo[j][0] + "," + demo[j][1] + ")";
            }             
            r = "SOLUTION: "+r;
        }
        else
            r = "NO SOLUTIONS";
        System.out.println(r);
    }    
}

Ini bukan solusi, tetapi reformulasi yang menghindari penyebutan secara eksplisit operasi swapping dan sortasi. Mulailah dengan menyortir seluruh daftar nama file gabungan dan versi bertukar mereka, dan mengidentifikasi setiap nama file dengan indeks dalam daftar itu. Lalu dua file bertetangga jika semua nama file lama di antara mereka telah dihancurkan, dan jika belum ada nama file baru di antara mereka. Masalah yang dirumuskan kembali adalah sebagai berikut:

Mengingat satu set menguraikan tepi diarahkan ( a , b ) dengan a , b ∈ { 1 , 2 , ... , 2 n } , apakah ada pemesanan ( a 1 , b 1 ) , ( a 2 , b 2 ) , . . . , ( a n , b n ) dari tepi ini sedemikian rupa sehingga$n$$(a, b)$$a, b \in \{1,2,…,2n\}$$(a_1, b_1), (a_2, b_2),...,(a_n, b_n)$

• $a_j$$b_i$$a_{i+1}$$j \le i$ , dan
• $b_j$$b_i$$a_{i+1}$$j \ge i+1$