Note: this sheet is available in the Startup File in our store.
Combinations and permutations are hard to understand and remember how they work. Each one has two variants, with or without repetition. There are four Excel functions with decent help text, but Excel will not teach you everything you need to know. You need to understand the concepts. What better way than to lay them out in a reference sheet?
In the process of creating this sheet, I learned and became more comfortable with the four types. I started by manually working out lists of permutations with repetition using r digits between 1 and N. These are the easiest to understand because repetition of digits is allowed, and rearrangement of the same digits is allowed. In other words, there are no limitations. This is like a padlock with three dials from 0 to 9, which has 10^3 = 1000 ways from 000 to 999 (call it a “permutation lock”?).
Each of the other three functions eliminates some items from this initial list. Combinations eliminate items from permutations, by not allowing the same set of digits to be rearranged; chocolate and vanilla is the same as vanilla and chocolate, order doesn’t matter. Combinations and permutations without repetition remove those items with any repeating digit; choosing unique items from a jar, you can’t choose the same item twice. By setting up a table with the four lists in columns, it’s easy to see the attrition of items by applying the logic of each type.
I listed out example data using numeric digits. Once I got the manual logic, I started working out the calculation logic digit by digit. The strategy is to calculate the permutations with repetition, and use columns to identify repeats and duplicates to be eliminated from the others.
Notation of these formulas in math texts uses N as the population count you’re selecting from, and r as the number of items you’re selecting from N. I’ll display the math formula for each (Alt-N,Z,S), and make N and r input cells named NPop and rSel, and formula PermA=PERMUTATIONA(NPop,rSel). NPop will allow whole numbers 1 to 9, rSel 1 to 4.
Table
The first column is an index of ordinal numbers, =N(Above)+1, to use in the digit formulas. MOD of [@index] against a power of NPop will determine when to increment the digit.
The first digit from the right is easy; use MOD([@index],NPop) unless it is 0, then use NPop. The first phrase hides values that are outside the set.
[D1] =IF([@index]>PermA,"",IF(MOD([@index],NPop), MOD([@index],NPop),NPop))
For the remaining digits, each value needs to repeat until the next power of NPop. Here I want to use the number from the column headers in row 11 in formulas by picking the right character, then VALUE to convert it to a number.
HdrVal =VALUE(RIGHT(F$11,1)) with active cell in column F
By referring to the header, the formula for digits 2, 3 and 4 is the same.
[D2], [D3], [D4] =IF(OR([@index]>PermA,rSel<HdrVal),"",IF(N(Above),IF( MOD([@index],POWER(NPop,HdrVal-1))=1, IF(Above=NPop,1,Above+1),Above),1))
The four digits are concatenated to create the item, which is also used in the PERMUTATIONA column.
[Dall] =CONCAT(Combinations[@[D4]:[D1]])
The next step is to identify the items to be removed from the other sets. These are two types, repeats and duplicates. Repeats are whenever the same value is in multiple output digits. Duplicates are when the same values are used in a different order. Both require a count of the values in each item.
There can be up to four output digits, but they can have values from 1 to 9, by my arbitrary rules. So next are nine columns, each doing COUNTIF on the 4-column digit range, for the value 1 to 9.
[V1], [V2], etc. =IF(OR([@index]>PermA,NPop<HdrVal),"", COUNTIF(Combinations[@[D4]:[D1]],HdrVal))
Repeats occur when the max of these nine COUNTIF columns is greater than 1. Another column checks this and flags “rep” all that match.
[repeat] =IF([@index]>PermA,"",IF(MAX(Combinations[@[V9]:[V1]])>1, "rep",""))
Duplicates uses another CONCAT, this one of the nine COUNTIF columns, to identify items with the same number of the same values; 112 and 121 both have one 2 and two 1’s; the CONCAT will be the same.
[Vall] =CONCAT(Combinations[@[V9]:[V1]])
The trick now is only to flag the second and subsequent duplicates, not the first. This is done by using an OFFSET range to look in, starting from the row above and up to the header. This flags “dup”.
[duplic] =IF([@index]>PermA,"",IF(COUNTIF(OFFSET([@[Vall]],-1,0,-(ROW()-ROW(Combinations[#Headers]))),[@Vall]),"dup",""))
With NPop 1 to 9 and rSel 1 to 4, the maximum number of rows required is then 9^4 = 6561. Once all columns were defined, I copied them down to 6561 rows.
Header
Above the table are two rows, one with the four functions, the other with a count of items in the four columns, COUNTIF(data column,">'0'"). The function result and the column count should always match, providing validation of the math. This sheet is a good visual and logical reference.
Commentaires