Combinations and Permutations

April 28, 2005 11:07 AM

Combinations and permutations are something that's starting cropping up a lot in my work and I need to rapidly elevate myself from utterly rubbish to vaguely proficient (example included).

My current problem is this: in an 8 player game I have a start screen from which the user chooses what character they wish to be. After they've chosen, that character disappears from the screen and the next player chooses from the remaining 7, etc etc. So I need to work out how many different screens are required to show all the different possible combinations of characters.

I'm not necessarily looking for an answer to this question, more direction as to how I can solve this, and other problems of this nature which will inevitably come my way. I do remember doing combs and perms at school and being utterly confused by it, so if anyone knows a more user friendly approach, I'd be most grateful....

thanks.

posted by forallmankind to computers & internet (10 comments total)

The formula you want in this simple case is called the factorial. There's lots more on configurations and permutations elsewhere at Mathworld.
posted by nicwolff at 11:16 AM on April 28, 2005

One formula is:
C(n,p) = n!/[(n-p)! * p!]
Where n is the number characters, and p is the number of characters picked. This is pronounced "n choose p." It is normally written with one number on top of the other:
(n)
(p)
with n and p enclosed in the same single pair of parentheses.

So, for example, if there are 8 characters, and 3 have been chosen, the number of possibilities is:
C(8,3)=8!/(5! * 3!)=(8*7*6)/(1*2*3)=56

You need to add up a bunch of these.

Alternately, you can just use this: on any given screen, every character is either present, or not present. Each of the 8 characters has a total of 2 states. So the total number of combinations is 2^8.
posted by CrunchyFrog at 11:27 AM on April 28, 2005

Oh, sorry - didn't read the question too well! CrunchyFrog's right, you need screens for all possible subsets which is 2^n. Or, not quite, since the last choice will be forced: 2^n - n. Although, then you need another n screens telling the last player that they've been assigned the remaining character... so, 2^n again.
posted by nicwolff at 11:43 AM on April 28, 2005

Except 2^n includes one screen which has no characters at all, which you probably don't need, so 2^n-1.
posted by DevilsAdvocate at 11:51 AM on April 28, 2005

These two links may help.
posted by Kwantsar at 12:02 PM on April 28, 2005

While there are 8! combinations of eight elements, it would be a waste to have 8! screens.

What you should do is have eight partial "screens", each showing one character. Here's a poor ASCII representation of that:
1 2 3 4 5 6 7 8

You should then combine those partial screens. To begin you combine all 8 and show this:
12345678

As each character was picked, you'd programmatically replace its partial screen with a "background" screen, which I'll denote as "9"

So if character 5 is picked, you make a new screen out of the partial screens 1 2 3 4 9 6 7 8, and show that:
12349678

Then if character 1 is picked:
92349678

Show you need one partial screen, that is to say, a picture, for each character, and one picture of the background, for a total of nine pictures.
posted by orthogonality at 12:14 PM on April 28, 2005

When I learned the "choose" word for the mysterious "combinations" I found it very helpful. Generally you're talking about final results: "how many different teams of 2 people can I form out of 4 possible people?". Saying "four choose two" made something click about the whole thing. It tells you how many final choices of 2 there are from among the 4.

The sort of question is what you do with the things you 'choose'. In the team example, you might imagine separating those two from the group. A common generic thing is to think of strings of 0's and 1's (as CrunchyFrog does). So "how many teams of 2 can I pick from 4 players" is the same as "how many 4-digit strings are there with two 1s?" The conceputal leap is that you start with 0000 and when you "choose" a digit, you flip it to 1.

How many 5-card poker hands are there? 52 choose 5. It's easier to imagine this as a 52-digit string of 0s where you pick 5 and flip the digit, instead of attacking it card-by-card.

If you did attack it card by card, you might think of it like this: you shuffle all the cards, and deal out the first 5 into your hand, and the other 47 into a pile. This was one of 52! ways you could have ordered the cards. However, the order they came into your hand wasn't important; there were 5! orderings (permutations) of those. And the ordering in the discard pile isn't important either, and there were 47! of those. Divide out the duplicates, so the result is 52!/ (5! 47!) which is "52 choose 5".

Say you were dealing them into 4 hands, then you'd have 52! / (5! 5! 5! 5! 32!). Each hand is unscrambled and the discard pile too. If you decide the order of the cards in the discard pile is significant then don't remove it -- you're left with 52! / (5! 5! 5! 5!) possible 'starting conditions' for a 4-hand game of poker. I think that's right...

The important thing with these kinds of problems is to stay flexible and try different conceptualizations, because often times a slight change to the problem will make you start over from scratch, or what is head-throbbingly hard with one method is dead simple with another.
posted by fleacircus at 12:39 PM on April 28, 2005

ForAllMankind,

It sounds like you are interestd in learning about combinatorics (wikipedia). I'm not sure how comfortable you are learning out of books, but I'd recommend A Course In Combinatorics by Lint and Wilson.
posted by rudyfink at 1:27 PM on April 28, 2005

what orthogonality said. for the hypothetical multiplayer game scenario it seems a bit overkill to make and store a screen for each possible permutation.
posted by juv3nal at 8:23 PM on April 28, 2005

A Course In Combinatorics is great book, but it might be a bit too much. I found it a bit tough going through it.

Discrete Mathematics and Its Applications is a great book on discrete math and includes a chapter (Counting) on permutations, combinations, and other combinatorial structures.

It's a handy, easy to read book. It might help with some of the material in the Lint and Wilson book.
posted by formless at 8:29 PM on April 28, 2005