Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I would like to assign 'x' individuals to 'y' groups, randomly. For example, I would like to divide 50 individuals into 100 groups randomly. Of course, with more groups than individuals many of the groups will have zero individuals, while some groups will have multiple individuals. That is fine. With random assignment, the distribution of the number of individuals per group should fit a Poisson distribution.

I feel like there should be a simple function in Mathematica for partitioning X things into Y groups randomly. I have searched and haven't found anything to do this. Please help!

share|improve this question
    
Welcome to Mathematica.SE! 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Take the tour and check the faqs! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! – Louis Feb 24 at 19:55

This does it:

x = 10000;
y = 50;
groups = PositionIndex[RandomChoice[Range[y], x]]

And you get the poisson:

QuantilePlot[PadLeft[Values[Map[Length, groups]], y],
  PoissonDistribution[x/y], Method -> {"ReferenceLineMethod" -> "Diagonal"}]

enter image description here

x = 1000000; y = 5000;
groups = PositionIndex[RandomChoice[Range[y], x]];
With[{vs = PadRight[Values[Map[Length, groups]], y]},
Show[ListPlot[Tally[vs].{{1, 0}, {0, 1/y}}, Filling -> Axis],
ListLinePlot[Thread[{#, PDF[PoissonDistribution[m = x/y], #]}] &[Range[Min[vs], Max[vs]]]]]]

enter image description here

share|improve this answer
x = 50;

myList = Range[x];

maxgroupSize = 5;

numberGroups = 100;

Table[DeleteDuplicates@RandomChoice[myList, maxgroupSize], numberGroups]

or

Table[RandomSample[myList, maxgroupSize], numberGroups]
share|improve this answer
randChoice[
   individuals_Integer?NonNegative,
   groups_Integer?Positive] :=
  RandomChoice[Range[groups], individuals];

choices = randChoice[50, 100]

(*  {58, 83, 34, 28, 25, 97, 6, 73, 28, 91, 6, 42, 93, 48, 56, 64, 20, \
88, 73, 11, 79, 65, 34, 3, 16, 18, 4, 18, 53, 30, 20, 97, 79, 30, 91, \
35, 35, 49, 31, 29, 80, 91, 87, 2, 23, 94, 27, 29, 87, 36}  *)

Tally[choices] // Sort

(*  {{2, 1}, {3, 1}, {4, 1}, {6, 2}, {11, 1}, {16, 1}, {18, 2}, {20, 
  2}, {23, 1}, {25, 1}, {27, 1}, {28, 2}, {29, 2}, {30, 2}, {31, 
  1}, {34, 2}, {35, 2}, {36, 1}, {42, 1}, {48, 1}, {49, 1}, {53, 
  1}, {56, 1}, {58, 1}, {64, 1}, {65, 1}, {73, 2}, {79, 2}, {80, 
  1}, {83, 1}, {87, 2}, {88, 1}, {91, 3}, {93, 1}, {94, 1}, {97, 2}}  *)
share|improve this answer

it looks like a Poisson:)

t = Tally[Flatten@RandomChoice[Range@100, {100000, 50}]][[All, 2]];
fdu = FindDistributionParameters[t, PoissonDistribution[u]];
Show[SmoothHistogram[t, PlotStyle -> Red], 
     Plot[PDF[PoissonDistribution[u /. fdu]][x], {x, Min@t, Max@t}, PlotStyle -> Blue]]

Mathematica graphics

share|improve this answer

Randomly partitioning a list into y groups is as easy, as splitting a random permutation of it at y-1 positions.

set = RandomSample[Range[50]] (* works with any list, though *)
split = Partition[{1}~Join~RandomChoice[Range[Length[set] + 1], 99]
          ~Join~{Length[set] + 1} // Sort, 2, 1]
set[[#,#2-1]]&@@@split;
share|improve this answer

This function is "stable" in the sense that elements will appear in sublists in the same order they appear in the supplied list.

Clear[randomSetPartition]; 
randomSetPartition[n_ /; IntegerQ[n], parts_] := 
  randomSetPartition[Range[1, n], parts]
randomSetPartition[individuals_List, parts_] := Module[
    { retVal, targets },
  retVal = Table[{}, {parts}];
  targets = RandomInteger[{1, parts}, {Length[individuals]}];
  MapThread[AppendTo[retVal[[#1]], #2] &, {targets, individuals}];
  retVal
]

This clears previous definitions, sets up a convenience function so you can use the small integers as a list of individuals rather than providing a specific list of individuals, then defines the workhorse. That function creates a list of empty bins, then successively inserts each individual into a uniformly randomly selected bin. Then it outputs the resulting set of bins.

Example usage:

randomSetPartition[{a, b, c}, 10]
randomSetPartition[3, 10]
(*
{{}, {}, {}, {}, {}, {c}, {b}, {}, {}, {a}}
{{}, {3}, {}, {2}, {}, {1}, {}, {}, {}, {}}
*)

randomSetPartition[Range[50], 100]
(*
{{}, {}, {28}, {38}, {37}, {21}, {}, {}, {}, {}, 
 {}, {}, {}, {48}, {41, 45}, {}, {}, {22}, {14}, {}, 
 {}, {}, {}, {}, {8}, {44}, {29}, {}, {}, {}, 
 {}, {11, 32, 40, 47}, {}, {10}, {}, {}, {}, {17}, {}, {2}, 
 {25}, {}, {}, {}, {23}, {49}, {}, {}, {4, 7, 35}, {}, 
 {}, {}, {31}, {18}, {}, {}, {}, {27}, {6}, {19}, 
 {}, {}, {24, 46}, {3}, {}, {}, {20}, {34}, {}, {12, 50}, 
 {}, {5}, {39}, {}, {30}, {}, {13, 43}, {}, {33}, {}, 
 {1, 42}, {}, {}, {}, {}, {}, {}, {}, {}, {}, 
 {}, {}, {}, {}, {15}, {9, 16, 26}, {}, {}, {36}, {}
}
*)

Possible bug detected: The lines "target = ..." and "MapThread ..." were originally the one line

AppendTo[retVal[[Evaluate[RandomInteger[{1, parts}]]]], #] & /@ individuals;

However, this line produces incorrect results. Since AppendTo[] is HoldFirst, the random integer is generated twice: once to figure out which bin to read for appending and another time to assign a bin back into the list of bins. This led to crazy things, like

randomSetPartition[{"a", "b", "c"}, 10]
(* {{}, {"a"}, {"c"}, {}, {}, {}, {}, {"a", "b"}, {}, {}} *)
(* Note:  ^                             ^  *)

which happened when the first random number said "append "b" to bin 2" and the second random number said "but overwrite bin 8".

There may be some convoluted way to get that to not happen with Evaluate[] and ReleaseHold[] magic -- but my fu is weak today. Instead, one could realize the random numbers into an array, targets, then use that array.

Possible directions of extension:

  • We could accept a list of weights to allow nonuniform assignment to bins.
  • This could be slow. I've never looked at the timing for inserting into depth 2 lists. It could be faster (for large inputs) to either make a list of {bin, individual} pairs, sort those, then construct the result iteratively. Maybe it would be better to make a map of bin -> individuals and read that out. Much testing could ensue.
  • For very sparse outputs, there have to be better ways to generate and return all the empties. For instance, use a method to determine how many bins will be nonempty, partition into that many bins, then randomly permute with the right number of empties. Some sort of sparse representation of the non-empties could be a good idea for speed and memory.
  • We could specify a sort order for the output bins, possibly different sorts for different bins.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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