Is it possible to find if a sequence exists in polynomial time in the following problem?

Question

I've been thinking about the following problem for a time, and I haven't found a polynomial solution for it. Only brute-fource. I've been trying to reduce an NP-Complete problem into it too with no sucess.

Here is the problem:

---

You have a sorted set $\{(A_1, B_1), (A_2, B_2), \ldots, (A_n, B_n)\}$ of positive integers pairs.

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

The following operation can be applied to a pair: Swap(pair). It swaps the elements of the pair, so $(10, 50)$ will become $(50, 10)$

When a pair in the set is swapped, the set automatically gets sorted again (the swapped pair is out of place and it will get moved into its place in the set).

The problem consist on see if there is a sequence that, starting on some pair, swaps the entire set, with the following condition:

After a pair is swapped, the next pair to be swapped has to be either the successor or the predecesor pair in the set.

---

It would be great to find a polynomial time solution to this problem, or a reduction of an NP-Complete problem into it.

Note:
It's already a decision problem. I don't want to know which the sequence is: only if a sequence exists.

Example of how the set gets sorted after swapping a pair

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

If I swap the first pair, it becomes to: $(5,6)$, and after sorting the set (placing the sorted pair in its new position), we have:

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

Then I have to swap either the $(3,4)$ (predecessor) pair or $(7,8)$ (sucessor), and repeat the process until all pairs are swapped (if possible).

Important:
You cannot swap an already swapped pair.
If there is a sequence of 'swap' operations, then all pairs has to be renamed to once and only once.

Example where isn't possible to swap all pairs

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

Answer 1

... I searched some patterns to build a reduction from a NPC problem, but didn't find a way to represent a "flow" with a "fork" ...

So (after some work) this is a polynomial algorithm ...

ALGORITHM

The starting list can be viewed as an array of $N*2$ consecutive "holes". For each initial pair $(a_j,b_j)$, put the "element" $b_j$ at hole number $a_j$. Each pair can be viewed as a directed edge from position $a_j$ to position $b_j$. A move consists in picking an element $b_j$ at position $a_j$ and moving it to its destination position $b_j$ (the destination hole becomes an unmovable peg). We delete the edge, and proceed to choose the next move which will start from one of the two nearest reachable elements $b_k$ from position $b_j$ (only holes between $b_j$ and $b_k$ are allowed). We must find a sequence of $N$ consecutive moves.

• For each $(a_j,b_j)$ consider $b_j$ (at array position $a_j$) as the starting element $start$.

  • For each $(a_k,b_k), a_k \neq a_j $ consider $a_k$ as the final element $end$ (the edge from position $a_k$ to position $b_k$ will be the final edge).

    • generate a sequence of moves from $start$ using the following criteria until you reach element $end$ (and a solution has been found), or a stop condition

When you make a move you fix a peg at position $b_j$ and the array is splitted in two partitions $L$ (left) and $R$ (right) and the only way to go from $L$ to $R$ (or from $R$ to $L$) is using an edge that jump across the peg. Set

• $edgesLR$ = number of edges from left to right (do not count the final edge)
• $edgesRL$ = number of edges from right to left (do not count the final edge)
• $flow$ = $edgesLR - edgesRL$

Cases:

A) if $| flow | > 1$ then one of the two partitions will become unreachable, stop

Now suppose that $end > b_j$, i.e. $end \in R$

B) if $flow = 1$ then there is an extra edge from left to right, you must go left (pick the nearest element of $L$), otherwise you will never reach $end$

C) if $flow = -1$ then there is an extra edge from right to left and whatever node you pick you will never reach $end$, stop

D) if $flow = 0$ you must go right (pick the nearest element of $R$), otherwise you will neve reach $end$

If $end < b_j$ ($end \in L$), B,C,D are inverted.

NOTE: when moving left or right, you must consider $end$ as a peg. For example, if you must go right, but the nearest element on $R$ is $end$ then the move is impossible (and you must proceed with another pair $(start,end)$)

Apply the same resoning at every move.

COMPLEXITY

The flows over each hole can be precalculated in O(N) and reused at every scan.

The loops are:

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 choices are made during the computation, so the complexity of the algorithm is $O(N^3)$

CODE

This is a working Java implementation of the algorithm:

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

Answer 2

This is not a solution, but a reformulation that avoids explicit mention of the swapping and sorting operations. Start by sorting the entire combined list of filenames and their swapped versions, and identify each filename with its index in that list. Then two files are neighbors if all the old filenames between them have already been destroyed, and if none of the new filenames between them have been created yet. The reformulated problem is the following:

Given a set of $n$ disjoint directed edges $(a, b)$ with $a, b \in \{1,2,…,2n\}$, is there an ordering $(a_1, b_1), (a_2, b_2),...,(a_n, b_n)$ of these edges such that

• if $a_j$ is between $b_i$ and $a_{i+1}$, then $j \le i$, and
• if $b_j$ is between $b_i$ and $a_{i+1}$, then $j \ge i+1$?