# 5p3 Permutation - Perfectly distributed Sets

• May 26th 2011, 09:10 PM
degger1
5p3 Permutation - Perfectly distributed Sets
Okay, I'm looking for a mathematical solution that may or may not exist. So I am asking smarter minds than mine. (I'm not a pure math guy, so my terminology may be all off.)

I'm starting with 5 items taken 3 at a time, and I'm looking for a way to match up the permutations in six sets.

5C3 gives me 10 possible combinations (abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.)

5P3 gives me 60 possible permutations which I put into an excel spreadsheet.

So, is there a method to break these 60 permutations into 6 unique sets of the 10 combinations, with each set perfectly distributed. (2 apiece starting with ABCDE, 2 apiece with the middle letter ABCDE and 2 apiece with the last letter ABCDE).

Sort of like the following: (abe, acd, bac, bed, cae, cdb, dba, dec eda, ecb) except my middle letters don't pan out and its only one of the six possible sets.

Any directions for a solution? I am totally open to brute force ideas using spreadsheets or an awesome statistical abacus. My current solution is a box of 60 notecard permutations hand-sorted on a table. Man, I should have paid better attention in statistics.
• May 26th 2011, 11:48 PM
bryangoodrich
You say "sort of like the following." Is that one of the cases you are looking at? I don't quite get what you mean by your description of "each set perfectly distributed" unless you just mean "two that start with a, two that start with b, two that start with c, ..."

To begin this problem, though, it is an easy way to think about how you get the 60 permutations. This draws on how permutations relate (similar or different) from combinations. In combinations, order doesn't matter. Thus, we have the three letters, in your case, of "abc". The permutation, however, is not concerned with order. Thus, we have "abc", but we also have "acb", "bac", "bca", "cab", "cba". Thus, each of the 10 combinations expands into a set of 6 permutations on that one combination. Now, if our goal is to get a set of ten that start with certain letters, we'll have to pick from amongst the different expansions of the combinations, since each combination lacks two of the other required letters in our set of 10 permutations we want to define. I don't think it is that difficult, though. If you notice how I rearranged "abc" it is systematic. We can expand every combination in like manner to produce a 6x10 grid. Each of the rows will contain 10 combinations unique from each of the other rows. From there you just need to swap "terms" to meet the requirements you have.
• May 27th 2011, 06:21 AM
degger1
I think that I found my answer, through old-fashioned sorting. (With a little help from excel)

I needed 6 sets of the 10 ABCDE combinations. Each had to have 2 of each of the starting letters, 2 of each of the center letters and two of each of the final letters.

After much hair-pulling work, I came up with the following:

1: acb, dac, eab, cde, ced, dea, bcd, bda, ebc, abe
2: ace, dab, ead, cda, ceb, dec, bce, bdc, eba, abd
3: acd, dae, eac, cdb, cea, deb, bca, bde, ebd, abc
4: cab, adc, aeb, dce, ecd, eda, cbd, dba, bec, bae

I'm guessing that there was an easier mathematical method to do this that I didn't know. However, I am still happy to have a result.
• May 27th 2011, 09:49 AM
bryangoodrich
Yeah, I don't know if there's an easy mathematical way, but I'm sure there is some sort of sort and search like algorithm that you can put Sudoku like constraints on to generate the 6x10 grid of 3-sequences you need. How to go about that, I don't know! In terms of combinatorics, the easy mathematical part is just getting the 10-set of combinations and generating the six 3-sequences from each combination in that 10-set. I think if you laid the 6x10 grid out, you should only need to shift the columns (row swaps) like you were doing a combination lock. Maybe not. It might require you to take cell 5x2 and swap it with 5x4 or something. My intuition is to think of it in terms of single swaps though, (shift all in column 2 down one and the last to the first position, sort of thing).
• May 27th 2011, 11:29 AM
degger1
Your theory is what I eventually tried and what eventually worked. Here was the process:

1. Set up base 6X10 grid with all permutation
2. Created 3 more 6X10 grids that each showed only the first, middle, or last letter in the permutation.
3. Set up a formula table that counted the number of each A,B,C,D, and E.
4. Shifted columns to resolve first letter table.
5. Shifted cells to resolve last and middle level.
6. When the formula tables showed 2 of each letter across the board, I rejoiced.