¿Es posible encontrar si existe una secuencia en tiempo polinómico en el siguiente problema?

He estado pensando en el siguiente problema por un tiempo, y no he encontrado una solución polinómica para él. Solo de origen bruto. He estado tratando de reducir un problema NP-Complete en él también sin éxito.

Aquí está el problema :

Tiene un conjunto ordenado de pares enteros positivos. $\{(A_1, B_1), (A_2, B_2), \ldots, (A_n, B_n)\}$

$(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$

La siguiente operación se puede aplicar a un par: Swap(pair). Intercambia los elementos del par, por lo que se convertirá en$(10, 50)$$(50, 10)$

Cuando se intercambia un par en el conjunto, el conjunto se ordena automáticamente de nuevo (el par intercambiado está fuera de lugar y se moverá a su lugar en el conjunto).

El problema consiste en ver si hay una secuencia que, comenzando en algún par, intercambie todo el conjunto, con la siguiente condición:

Después de intercambiar un par, el siguiente par que se debe intercambiar debe ser el par sucesor o el par predecesor del conjunto.

Sería genial encontrar una solución de tiempo polinómico para este problema, o una reducción de un problema NP-Complete en él.

Nota:
ya es un problema de decisión. No quiero saber cuál es la secuencia: solo si existe una secuencia.

Ejemplo de cómo se ordena el conjunto después de cambiar un par

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

Si cambio el primer par, se convierte en: , y después de ordenar el conjunto (colocando el par ordenado en su nueva posición), tenemos:$(5,6)$

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

Luego tengo que intercambiar el par (predecesor) o (sucesor), y repetir el proceso hasta que se intercambien todos los pares (si es posible).( 7 , 8 $(3,4)$$(7,8)$

Importante:
No puede intercambiar un par ya intercambiado.
Si hay una secuencia de operaciones de 'intercambio', entonces todos los pares deben renombrarse una vez y solo una vez.

Ejemplo donde no es posible intercambiar todos los pares

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

... Busqué algunos patrones para construir una reducción de un problema de NPC, pero no encontré una forma de representar un "flujo" con un "tenedor" ...

Entonces (después de un poco de trabajo) este es un algoritmo polinómico ...

ALGORITMO

La lista de inicio puede verse como una matriz de " agujeros " consecutivos . Para cada par inicial ( a j , b j ) , coloque el " elemento " b j en el hoyo número a j . Cada par puede verse como un borde dirigido desde la posición a j hasta la posición b j . Un movimiento consiste en elegir un elemento b j en la posición a j y moverlo a su posición de destino b $N*2$$(a_j,b_j)$$b_j$$a_j$$a_j$$b_j$$b_j$$a_j$$b_j$(el agujero de destino se convierte en una clavija inamovible ). Eliminamos el borde y procedemos a elegir el siguiente movimiento que comenzará desde uno de los dos elementos alcanzables más cercanos desde la posición b j (solo se permiten agujeros entre b j y b k ). Debemos encontrar una secuencia de N movimientos consecutivos.$b_k$$b_j$$b_j$$b_k$$N$

• Para cada considere b j (en la posición de la matriz a j ) como el elemento inicial s t a r t .$(a_j,b_j)$$b_j$$a_j$$start$

  • Para cada considere a k como el elemento final e n d (el borde desde la posición a k hasta la posición b k será el borde final).$(a_k,b_k), a_k \neq a_j$$a_k$$end$$a_k$$b_k$

    • generar una secuencia de movimientos desde utilizando los siguientes criterios hasta llegar al elemento e n d (y se ha encontrado una solución), o una condición de detención$start$$end$

Cuando realiza un movimiento, fija una clavija en la posición y la matriz se divide en dos particiones L (izquierda) y R (derecha) y la única forma de ir de L a R (o de R a L ) es usando un borde que salta a través de la clavija. Conjunto$b_j$$L$$R$$L$$R$$R$$L$

• = número de aristas de izquierda a derecha (no cuente la arista final)$edgesLR$
• = número de aristas de derecha a izquierda (no cuente la arista final)$edgesRL$
• = e d g e s L R - e d g e s R $flow$$edgesLR - edgesRL$

Casos:

A) si entonces una de las dos particiones se volverá inalcanzable, deténgase$| flow | > 1$

Ahora suponga que , es decir, e n d ∈ $end > b_j$$end \in R$

B) si entonces hay un borde adicional de izquierda a derecha, debe ir a la izquierda (elija el elemento más cercano de L ), de lo contrario nunca llegará a e n $flow = 1$$L$$end$

C) si entonces hay un borde adicional de derecha a izquierda y cualquier nodo que elija nunca llegará a e n d , pare$flow = -1$$end$

D) si debe ir a la derecha (elija el elemento más cercano de R ), de lo contrario nunca llegará a e n $flow = 0$$R$$end$

Si ( e n d ∈ L ), B, C, D están invertidos.$end < b_j$$end \in L$

NOTA: cuando se mueve hacia la izquierda o hacia la derecha, debe considerar como una clavija. Por ejemplo, si debe ir a la derecha, pero el elemento más cercano en R es e n d, entonces el movimiento es imposible (y debe proceder con otro par ( s t a r t , e n d ) )$end$$R$$end$$(start,end)$

Aplica la misma resonancia en cada movimiento.

COMPLEJIDAD

Los flujos sobre cada orificio pueden calcularse previamente en O (N) y reutilizarse en cada exploración.

Los bucles son:

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     

No se realizan elecciones durante el cálculo, por lo que la complejidad del algoritmo es $O(N^3)$

CÓDIGO

Esta es una implementación funcional de Java del algoritmo:

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);
    }    
}

Esta no es una solución, sino una reformulación que evita la mención explícita de las operaciones de intercambio y clasificación. Comience ordenando toda la lista combinada de nombres de archivo y sus versiones intercambiadas, e identifique cada nombre de archivo con su índice en esa lista. Luego, dos archivos son vecinos si todos los nombres de archivo anteriores entre ellos ya se han destruido, y si ninguno de los nuevos nombres de archivo entre ellos se ha creado todavía. El problema reformulado es el siguiente:

$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$
• $b_j$$b_i$$a_{i+1}$$j \ge i+1$