I have a list of elements of different values, say 0 to 3. I want to split it into a certain number of sub lists, each accepting only certains elements. The sub lists may not always have the same length.
For example, I have a list of 12 elements: [0,0,0,1,1,1,2,2,2,3,3,3]. I want to split it into 3 sub lists:
- One that accepts all elements.
- One that only accepts 1, 2 and 3. That list could be
[1,1,2,2]but not[0,0,2,3]. - One that only accepts 0, 2 and 3. That list could be
[0,0,2,3]but not[1,1,2,2].
A sub list that accepts elements doesn't mean it needs to contain these elements.
I tried filling each sub list in order with random elements from the parent list meeting the sub list criteria. With the example above, it could go like this:
- Fill the 1st list:
[0,0,0,2]. Parent list is now[1,1,1,2,2,3,3,3]. - Fill the 2nd list:
[2,2,3,3]. Parent list is now[1,1,1,3]. - Try to fill the 3rd list: only
[1,1,1,3]is left but this list can't take 1s. Start again.
Because of the use of random this could never end in the worst case.
The algorithm must give uniform results, all combinations of sub lists having the same probability to be chosen.
Context: This is for a card game where the computer plays using Information Set Monte Carlo Tree Search. One step is too make a randomized state of the game from the point of view of a player. All cards unknown to the observer are shuffled together (making the parent list) and redistributed (the sub lists). In this particular game, the player has a way to know that other players may not have cards of a particular suit, so in the randomized state step, no cards of these suits should be distributed to those players (hence why sub lists can have certain values).
In this context there will always be 2 or 3 sub lists, and each sub list will always have between 1 and 13 elements. The difference in the size of two sub lists is never greater than 1.
