Suppose we have a binary string $s$. We wish to partition this string in a series of $0$s followed by $1$s (alternatively: we wish to sort), using only one operation: moving three consecutive elements to the end.

E.g. if our string is $ABCDEFGH$ we can do our operation at index $1$ to get $DEFGHABC$. If we did it at index $4$ we'd get $ABCGHDEF$.

I'm interested in optimal solutions - that is with the least amount of moves. I have a working algorithm using IDA* with heuristic "# of groups of ones with length $\leq 3$ before the final zero", with the logic that each such a group requires at least one move to fix. An example optimal solution (where ^ indicates where a block was chosen to move to the end):

1101101011101011010010010011                               
                       ^                                   
1101101011101011010010011100                               
                     ^                                     
1101101011101011010011100001                               
              ^                                            
1101101011101010011100001110                               
           ^                                               
1101101011110011100001110010                               
                        ^                                  
1101101011110011100001110001                               
     ^                                                     
1101111110011100001110001010                               
  ^                                                        
1111110011100001110001010011                               
                     ^                                     
1111110011100001110000011101                               
                       ^                                   
1111110011100001110000001111                               
               ^                                           
1111110011100000000001111111                               
        ^                                                  
1111110000000000001111111111                               
   ^                                                       
1110000000000001111111111111                               
^                                                          
0000000000001111111111111111 

However, this algorithm is exponential and not feasible for larger strings. After studying quite some optimal solutions, especially tough ones like above, I can't immediately think of an optimal algorithm. Moves can be quite non-trivial.

Is there a feasible optimal algorithm? Or is this problem hard?

  • I'm not yet sure that "# of groups of ones with length ≤ 3 before the final zero" is an admissible heuristic -- aren't there possibly situations where $k$ copies of 101, which contains 2 such groups, could be solved with fewer than $2k$ moves? – j_random_hacker Jun 24 at 16:44
  • Within any consecutive subsequence of moves that do not overlap (that is, every pair of starting positions is separated by at least 3), the order that two moves of the same triple pattern take place has no effect. That means that there is never any point investigating a solution in which we move a triple with pattern $x$ at position $p$, if (a) our most recent previous move of an $x$-patterned triple had starting position $q \ge p+3$ and (b) all moves performed between then and now were nonoverlapping. This rule won't make anything polynomial-time, but might reduce the explosion a bit. – j_random_hacker Jun 24 at 16:59

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.