#StackBounty: #algorithms #sorting #strings #binary Partitioning through block moves to the end

Bounty: 50

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?


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.