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?