How can I shuffle a list without randomness, and guarantee that a portion of elements will eventually appear on one side?

Question

Given a list of elements, does a shuffling algorithm exist that will guarantee that eventually a selected half portion will be on one side, and the remainder on the other?

Example: { 4, 3, 10, 7, 2, 9, 6, 8, 1, 5 }

Given the set above, I'd like to have a mixing algorithm that eventually moves the marked ones to the left, even though the algorithm itself has no idea what is and isn't "marked."

   { 4, 3, 10, 7, 2, 9, 6, 8, 1, 5 }
     X       X           X  X       X

Acceptable results would be:
   { 4, 10, 9, 6, 1, 3, 7, 2, 8, 5 }
   { 1, 9, 10, 4, 6, 2, 8, 5, 7, 3 }
   { 1, 4, 9, 10, 6, 3, 7, 5, 8, 2 } etc

Difficulty: The algorithm shouldn't use random numbers to mix the contents, it should be an iterative process. So Fisher-Yates is out.

Answer 1

Split your list into two lists - flagged and unflagged. Shuffle both sublists, and put the flagged on one side and the unflagged on the other. Now you can use any shuffling algo you want.

Answer 2

Would std::next_permutation() be what you want? (Since it creates all possible permutations, it will, eventually, also put the marked once to the left.)