#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!!!

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