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

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.)

Answer 2

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 3

Something like next_permutation will do the job, and (eventually) so will something like bogo sort. Either will eventually produce every possible permutation, including all the permutations you consider acceptable (along with some arbitrary number you don't).

Bogo sort shows that your: "The algorithm shouldn't use random numbers to mix the contents, it should be an iterative process. So Fisher-Yates is out." is a false dichotomy. Bogo sort mixes randomly and it's iterative.

Answer 4

I think you are looking for an algorithm that: * Can be used to display a iterative process to a user that looks something like shuffling * Ends up with the original set separated into 2 (preselected) groups but randomly ordered within each group

Seems to me that something simple might suit you well consider for your ten numbers and using the terminology marked/unmarked for the groups this algorithm:

1. Randomly select two members of the set
2. if swapping these two members would result in a marked number 
     being moved into positions 1-5 then forget about this swap and start again
3. Swap these elements
4. Check if positions 1-5 have ONLY marked elements, 
     if so you are done, otherwise start again

This doesn't give an efficient statistically good shuffle like Fisher-Yates but does give you a good looking on screen mix up.