Math help for the right brained

April 28, 2007 1:10 PM

I have a math question involving combinations and sets.

I just participated in my first MeFi CD swap, and I got to wondering if there was an algorithmic way to make sure each round's swap sets are as unique as possible. IANAMathPerson, so here's a wordy explanation of the problem:

Let's say we have 9 people who are going to be split up into groups of 3 over several rounds. How can I determine how many unique combinations there are?

For an example of this size, it's trivial by hand:
Round 1: [ABC] [DEF] [GHI]
Round 2: [ADG] [BEH] [CFI]
Round 3: [AEI] [BFG] [CDH]
Round 4: [AFH] [BDI] [CEG]

4 rounds, no one ever shares a set with the same person twice, and there are no further unique solutions. For larger sets of size N and subsets of size K, is there an equation that will tell me how many unique combinations can be made?

posted by sonofslim to grab bag (21 comments total)

There's not an easy way to do it mathematically, but you could program something that would create groups along your rules very simply.

I'm not sure why you're mentioning subsets.
posted by tylermoody at 1:28 PM on April 28, 2007

The total number of ways that nine items can be ordered is 9 factorial.

If you take such a list and divide it into threes, then you have to weed out all the cases where a given set of three are the same members but in different orders. The number of reorderings of three members is 3 factorial.

So the total is 9!/(3!*3!*3!) == 1680
posted by Steven C. Den Beste at 2:13 PM on April 28, 2007

Off the top of my head, isn't the answer:

(N c K) * ((N-K) c K) * ((N-2K) c K) * ... * (K c K) / K!

whenever N is divisible by K?

That is, (9 combination 3) times (6 combination 3) times 1, all divided by 3 factorial, to account for re-orderings among the groups but not within them?
posted by kid ichorous at 2:18 PM on April 28, 2007

My solution permits [CDE] and [CDF] as being acceptable unique cases. Excluding all cases where any two have previously been in a group is more difficult and I'm not sure how you'd calculate that.
posted by Steven C. Den Beste at 2:19 PM on April 28, 2007

Hmm, SCDB, my method has an extra 3! on the bottom, giving 240 rather than 1680. This extra 3! is because you can reorder the groups themselves, a la:

[ABC][DEF][GHI] ~ [DEF][ABC][GHI]
posted by kid ichorous at 2:28 PM on April 28, 2007

To further strip this down so that no two members can ever occupy a group twice is nontrivial. I'll have to think about that a little!
posted by kid ichorous at 2:30 PM on April 28, 2007

SCDB fails, overcounting by a factor of more than 400.

The answer to the question "How many ways can a group of N people be broken up into K groups" is called a Stirling Number of the Second Kind, S(N,K). It's not as easy to compute as a binomial coefficient, but it's exceedingly well-studied.

Your problem, however, where we insist on all groups having the same size is a problem of "combinatorial designs," and in general it's hard. However, the answers for small values are here. (Site has shitty MIDI music, I'm sorry.)

(For N=15 broken into blocks of three this problem is widely known as Kirkman's Schoolgirl Problem).
posted by Wolfdog at 2:34 PM on April 28, 2007 [1 favorite]

Nice, Wolfdog! That "no two members" condition made it a lot harder.

Also, that music just screams "social golfer problem." As in, it's time for an intervention.
posted by kid ichorous at 2:44 PM on April 28, 2007

Yes, it is the non-trivial case I am puzzling over.

Here's some more info, if it makes my question and the reasoning behind it any clearer:

I've already written a script that generates permutations of a set. If a permutation passes the uniqueness test, it gets added to the list of known solutions. (The test is agnostic to the order of the groups, or the order within any group.)

The challenge is, what happens when I've exhausted all of the unique permutations? I'd want to come up with a permutation that has the least amount of repetition with a prior round. In this example, round 5 would ideally contain just 2 pairs that have already shared a group. So I added a ranking function to my script, which orders permutations based on how many past pairings they repeat.

The nut of my question, then, is how do I know when to switch from "find unique answer" behavior to "find next best answer" behavior. If I knew when I'd already found the maximum # of unique permutations, this would be easy.

The algorithm that generates permutations does it cyclically, so stepping one at a time from ABCDEFGHI to a permutation that fits my rules would take a very long time. It would be absurdly inefficient for any non-trivial number of elements. Thus, my program actually looks at permutations in a random order -- turns out this is a pretty quick way to find solutions. But it also means I can't search exhaustively for unique permutations. At some point I need to fall back to behavior #2. If I knew when that was ahead of time, I wouldn't have to waste cycles looking for solutions that don't exist.
posted by sonofslim at 2:49 PM on April 28, 2007

When I say "hard" I mean "I'm pretty sure that the site I've linked gives all values that are currently known." It also gives you the breakdown into sets if you click on the numbers, so unless you're deadset on reproducing the work by yourself...

(To be clear, the linked site does address the "no repeated pairings" condition.)
posted by Wolfdog at 2:54 PM on April 28, 2007

Bummer, I was really hoping for a pretty solution. Thanks for warning me before I spent much more time puzzling over this, though!
posted by sonofslim at 3:58 PM on April 28, 2007

I was playing with Mathematica to see if I could come up with an algorithmic way to do this, and I made some progress you might be able to build upon.

I used Robert M. Dickau's BellList function outlined here.

I wrote a function to separate out the three-part partitions of the set of nine elements from the BellList.

Of those three-part partitions, only 280 contain three-element subsets.

You could build a list from the output, pick one of the 280 and then filter out from the remaining 279 those partitions which do not follow your uniqueness criteria.

I'm still a little puzzled about this criteria given the example you provide (I think there should be more than four permutations — for example, [ADH][BEG][CFI] would work for the second round, right?).

In any case, you'd do something like partitionList = {}; at the top and partitionList = Append[partitionList, BellList[9][[i]]]; at the bottom of the code, where the tally variable is incremented.

Once you have partitionList you have a set of partitions on which you can apply your rules.

Here's the code:

In[3] := BellList[1] = {{{1}}};(*the basic case*)

In[4]:= BellList[n_Integer?Positive] := BellList[n] = (* do some caching *)

 Flatten[
  Join[
   Map[ReplaceList[#, {S__} -> {S, {n}}] &, BellList[n - 1]],

   Map[ReplaceList[#, {b___, {S__}, a___} -> {b, {S, n}, a}] &, BellList[n - 1]]], 1]

In[5]:= Dimensions[BellList[9]]
Out[5]= {21147}

In[9]:=
tally = 0;
For[i = 1, i ≤ Length[BellList[9]], Increment[i],
 If[Length[BellList[9][[i]]] == 3,
  flag = True;
  For[j = 1, j ≤ 3, Increment[j],
   If[ Length[BellList[9][[i]][[j]]] ≠ 3, flag = False; j = 4; ]
  ]
  If[flag, Print[BellList[9][[i]]]; Increment[tally];]
 ]
];
Print[tally];

From In[9]:=
{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
{{1, 2, 4}, {3, 5, 6}, {7, 8, 9}}
{{1, 2, 5}, {3, 4, 6}, {7, 8, 9}}
{{1, 2, 6}, {3, 4, 5}, {7, 8, 9}}
{{1, 3, 4}, {2, 5, 6}, {7, 8, 9}}
{{1, 3, 5}, {2, 4, 6}, {7, 8, 9}}
{{1, 3, 6}, {2, 4, 5}, {7, 8, 9}}
{{1, 4, 5}, {2, 3, 6}, {7, 8, 9}}
{{1, 4, 6}, {2, 3, 5}, {7, 8, 9}}
{{1, 5, 6}, {2, 3, 4}, {7, 8, 9}}
...
{{1, 6, 9}, {2, 7, 8}, {3, 4, 5}}
{{1, 7, 8}, {2, 6, 9}, {3, 4, 5}}
{{1, 7, 9}, {2, 6, 8}, {3, 4, 5}}
{{1, 8, 9}, {2, 6, 7}, {3, 4, 5}}
280
posted by Blazecock Pileon at 4:29 PM on April 28, 2007

So far, so good, BP, but now from a list of 280 partitions, you have to choose a maximal subset subject to the criterion that no two elements are ever grouped together in more than one of the partitions you select. That's the hard part.
posted by Wolfdog at 4:39 PM on April 28, 2007

Also, here's a shorter version of what you've already done:

< discretemath`br> Select[KSetPartitions[9, 3], Length /@ # == {3, 3, 3} &]
posted by Wolfdog at 4:44 PM on April 28, 2007 [1 favorite]

Oh, that's just great.

<<DiscreteMath`
Select[KSetPartitions[9,3],Length/@#=={3,3,3}&]
posted by Wolfdog at 4:46 PM on April 28, 2007

All that work! I wish I knew how to use Mathematica better...
posted by Blazecock Pileon at 4:49 PM on April 28, 2007

Very elegant Wolfdog! Yes, like BP, I wish my Mathematica foo was better. This whole thread has been quite illuminating.
posted by rasputin98 at 5:25 PM on April 28, 2007

So... full disclosure, I failed college calculus twice and this discussion was over my head by the third answer. What I'm gathering is that it would be a better use of time (and probably easier) to work on a good best-case-failure algorithm than to try to crack this nut, right?
posted by sonofslim at 10:43 PM on April 28, 2007

If you need to know the largest number of rounds that can be run according to your criteria - that is, "What's the very largest number of rounds can we run before some two people have to be in the same group again" - then, yes, unfortunately, finding that number is a computationally intractable problem.

But the fact that finding the largest possible number (and being certain it's largest) is hard doesn't mean you can't have some success constructing reasonably large solutions. If I were doing this for a practical application, here's how I'd most likely start:

First,

1. Construct one set of swap groups for the first round. (You might as well just number the people in the group and put them in groups by order for the first set, just like you did in your example.)

Then,

2. Check to see if it's possible to add another round to the rounds we've already done.
3. If so, add a round by constructing a new set of swap groups compatible with the ones we already have. If there are any choices to be made, make them randomly. Then return to step 2.
3. Otherwise, stop and print out the list.

Now, it's unlikely you'll get a list of the largest possible number of rounds right off the bat. But because of the randomization, you can rerun this until you get a list with as many rounds as you want, or you become convinced that such a list is very unlikely to exist. I believe you'll find that reasonably large solutions turn up fairly quickly; then it's just a matter of how many times you want to rerun it trying for something better.

Step 2, the checking part, shouldn't be too hard if you maintain a list of all pairs of people that have been grouped together up to the current point.
posted by Wolfdog at 6:47 AM on April 29, 2007

I found this paper about the social golfers problem; looks interesting and I'm hoping I can make my way through the math. * sharpens pencil *

I do have a real-world application in mind for this, I'm sure I would have ended up chasing my tail without everyone's help. Interesting stuff to think about nonetheless. Thanks a bunch!
posted by sonofslim at 8:34 AM on April 29, 2007

With a set of size N and subsets of size K, consider the subsets of which you are a member. You have K-1 fellow members in each set. And your fellow members must be different in each set. So there can be no more than (N-1)/(K-1) rounds, otherwise you would be grouped with someone in more than one round.
posted by euphotic at 4:22 AM on May 11, 2007