2
$\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$
  • 1
    $\begingroup$ @Apass.Jack I added some context, hope it helps. $\endgroup$ – Nicolas Jan 17 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$ – j_random_hacker Jan 18 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$ – j_random_hacker Jan 18 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$ – j_random_hacker Jan 23 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$ – j_random_hacker Jan 27 at 11:07
0
$\begingroup$

I'd start with the more restricted lists and assign the first hand, which could get any card combination last.

$\endgroup$
  • 4
    $\begingroup$ I don't think that this will select each possible assignment with equal probability, which is what I think the question means with "uniform results". If you think that this method does select uniformly, please explain why. $\endgroup$ – Discrete lizard Jan 17 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.