3
$\begingroup$

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.

$\endgroup$
16
  • 1
    $\begingroup$ @Apass.Jack I added some context, hope it helps. $\endgroup$
    – Nicolas
    Jan 17, 2019 at 20:56
  • 1
    $\begingroup$ Are the lengths of the sublists specified as part of the problem, or are you allowed to make them all any size you want? Either way, you can solve the problem of finding a solution in polynomial time, as it's the Assignment Problem (finding a maximum matching in a bipartite graph) in disguise. Not sure how to choose uniformly randomly from the set of all such solutions though. $\endgroup$ Jan 18, 2019 at 16:55
  • 1
    $\begingroup$ OK, please edit your question to include that constraint. The Assignment Problem can be solved efficiently whenever each sublist ("worker") has a fixed minimum and maximum number of elements ("tasks") that can/must be assigned to it, and fortunately the constraint you gave can be expressed this way :) $\endgroup$ Jan 18, 2019 at 17:13
  • 1
    $\begingroup$ Suppose there are $n$ elements, and $k$ sublists ($k$ is 2 or 3). We will make a bipartite graph consisting of 2 sets of vertices, "tasks" ($A$) and "workers" ($B$). Make a "task" vertex in set $A$ for each element (so $n$ of these). For each sublist, make $\lceil n/k \rceil$ "worker" vertices in set $B$, and add an edge between each of these "worker" vertices and every "task" vertex in set $A$ that corresponds to an element that could be assigned to this sublist. Finally run the Hungarian algorithm, or other algorithm for solving the Assignment Problem, on this graph. $\endgroup$ Jan 23, 2019 at 14:57
  • 1
    $\begingroup$ If you know the specific sizes of each sublist (I tried to ask this in my original question), then of course just use those. $\endgroup$ Jan 27, 2019 at 11:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.