27
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Is the list sorted after you rename the file and before you choose the next file to rename? Can you rewrite the sorting condition as: $(A,B,C) < (A',B',C')$ iff ($A < A'$) or ($A=A'$ and $B<B'$) or ($A=A'$ and $B=B'$ and $C < C'$)? $\endgroup$ – mjqxxxx Jan 31 '11 at 1:45
  • 3
    $\begingroup$ Assignment problems are not welcome on cstheory.stackexchange.com in general. $\endgroup$ – Tsuyoshi Ito Jan 31 '11 at 4:41
  • 3
    $\begingroup$ Hmm, I am not sure. Usually the logic here is that it is not a good practice to answer typical homework questions because doing so will ruin the purpose of homework for someone in the future. But in this case, the problem does not look like a typical problem. $\endgroup$ – Tsuyoshi Ito Jan 31 '11 at 4:46
  • 2
    $\begingroup$ maybe if you give a motivation different than "it was a homework", people could get interested and it won't be closed. What could be a possible application of this? $\endgroup$ – Marcos Villagra Jan 31 '11 at 7:58
  • 2
    $\begingroup$ about reformuulating the problem, you can forget about files and see it this way. You have a set of pairs of positive integers $A=\{(x_1,y_1),\dots,(x_n,y_n)\}$, and the rules are the same as you put it. Initially is sorted in the first column, then you start renaming the points. $\endgroup$ – Marcos Villagra Jan 31 '11 at 8:46
16
+50
$\begingroup$

... 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);
    }    
}
$\endgroup$
  • $\begingroup$ This is an interesting approach. In general, whenever you use an edge $(a,b)$, there must be equal (or differing by one) numbers of unused edges crossing $b$ in each direction; and if the numbers differ by one, you know which edge you must take next. When the numbers are equal, you have a choice, which you must resolve by testing both options. It seems like an efficient enough search strategy, but how do you know it's polynomial in the worst case? I.e., how do you know you will only encounter $O(\log n)$ choices where the number of unused crossing edges in each direction is equal? $\endgroup$ – mjqxxxx Feb 3 '11 at 18:24
  • $\begingroup$ @mjqxxxx ... I rewrote the whole answer to match the Java algorithm ... $\endgroup$ – Marzio De Biasi Feb 4 '11 at 16:12
  • $\begingroup$ @mjqxxxx ... ok, finally I got it ... :-) $\endgroup$ – Marzio De Biasi Feb 5 '11 at 13:59
  • 2
    $\begingroup$ This looks correct and very elegant to me. Once you use an edge $(a,b)$, you can no longer "walk" across $b$; the only remaining transitions across $b$ are the unused "jumps" (directed edges) crossing it, all of which you must use. If the final edge $(a_n, b_n)$ is specified, then you need to wind up on the same side of $b$ as $a_n$. There is then only one possible direction to walk after each edge, since an odd (even) number of jumps will leave you on the opposite (same) side you initially walked to. So testing each choice of starting and ending edges can be done in polynomial time. $\endgroup$ – mjqxxxx Feb 8 '11 at 22:06
  • 1
    $\begingroup$ This is a beautiful algorithm. It never occurred to me to fix the last move first. Minor points: (1) As mjqxxxx wrote, end must be a_k. Otherwise the condition “end>b_j” is wrong. (2) Either the definition of “flow” has to be negated, or the cases B and C have to be swapped. $\endgroup$ – Tsuyoshi Ito Feb 10 '11 at 0:51
10
$\begingroup$

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$?
$\endgroup$
  • 2
    $\begingroup$ +1. This is a much simpler way to state the equivalent problem. Just one clarification: the edges (a,b) are directed (in the sense that the edge (a,b) and the edge (b,a) have different meanings). $\endgroup$ – Tsuyoshi Ito Feb 1 '11 at 18:53
  • $\begingroup$ @Tsuyoshi: thanks; I edited to say 'directed'. $\endgroup$ – mjqxxxx Feb 1 '11 at 19:10
  • $\begingroup$ As I understand the phrase "$b$ is between $a$ and $c$" means $a\leqslant b\leqslant c$. So I guess it's worth changing the former notation by the latter one. $\endgroup$ – Oleksandr Bondarenko Feb 2 '11 at 18:43
  • $\begingroup$ @Oleksandr: Here “b is between a and c” means “either a<b<c or c<b<a.” $\endgroup$ – Tsuyoshi Ito Feb 2 '11 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.