Looking for a good reference on calculating permutations

Question

Hi,

As a programmer, I frequently need to be able to know the how to calculate the number of permutations of a set, usually for estimation purposes.

There are a lot of different ways specify the allowable combinations, depending on the problem at hand. For example, given the set of letters A,B,C,D

1. Assuming a 4 digit result, how many ways can those letters be arranged?

2. What if you can have 1,2,3 or 4 digits, then how many ways?

3. What if you are only allowed to use each letter at most once? twice?

4. What if you must avoid the same letter appearing twice in a row, but if they are not in a row, then twice is ok?

Etc. I'm sure there are many more.

Does anyone know of a web reference or book that talks about this subject in terms that a non-mathematician can understand?

Thanks!

Answer 1

First of all the topics you are speaking of are

• Permutations (where the order matters)
• Combinations (order doesn't matter)

I would recommend Math Tutor DVD for teaching yourself math topics. The "probability and statistics" disk set will give you the formulas and skill you need to solve the problems. It's great because it's the closest thing you can get to going back to school, because a teacher solves problems on a white board for you.

I've found a clip on the Combinations chapter of the video for you to check out.

Answer 2

It all depends on how simply do you need the explanation to be.

The topic you are looking for is called "Permutations and Combinations".

Here's a fairly simply introduction. There are dozens like this on the first few pages from google.

Answer 3

Assuming a 4 digit result, how many ways can those letters be arranged?

when picking the 1st digital , you have 4 choices ,which is one of A, B , C and D ; it is the same when picking the 2nd, 3rd ,4th since repetition is allowed: so you have total : 4*4*4*4 = 256 choices.

What if you can have 1,2,3 or 4 digits, then how many ways?

It is easy to deduce from question 1.

What if you are only allowed to use each letter at most once?

When pick the 1st digital , you have 4 choices ,which is one of A , B , c and D ; when picking the 2nd , you have 3 choice except the one you have picked for the 1st ; and 2 choices for 3rd , 1 choices for the 4th. So you have total : 4 * 3 * 2 * 1 = 24 choice.

The knowledge involving here include combination , permutation and probability. Here is a good tutorial to understand their difference.

Answer 4

If you need to do more than just count the number of combinations and permutations, if you actually need to generate the sequences, then Donald Knuth's books Generating all combinations and partitions and Generating all tuples and permutations. He goes into great detail regarding algorithms subject to various restrictions, looking at the advantages and disadvantages of different solutions for each problem.