See bottom for free download!
It's about time I wrap this topic up and move on, don't you think? I'm a little sad to leave it, like the end of a good vacation, but I have to appreciate how fun and invigorating it's been. In the end, the thrill of invention only comes with a successful result, which I am ready to celebrate with the introduction of the last two of the four functions.
This is admittedly an esoteric case; most "normal people" won't have practical use for these functions. The reason I tackled it is for intellectual integrity. Whether it has use or not can only be told from understanding, which comes from transparency. The concepts and native functions exist in obscurity, I am elucidating them.
But the result is greater than the direct output. Solution development is a springboard to learning and capability. I've become more comfortable using arrays and recursion, and I've refined my standards for function integrity. That's what I want to share with you now.
Recap
There are many ways that we routinely select a certain number of items from a given set: coin tosses; digital locks; ice cream flavors; pool; bingo; the lottery, and so forth. With any such case, the two questions to ask are:
does the order of selection matter?
is repetition allowed?
The highest possible number of selections is when order matters, called permutations, WITH repetition. The number of selections goes down from there when repetitions are not allowed, and when order doesn't matter. Thus, combinations are a subset of permutations; "WITHOUT repetition" are subsets of "WITH repetition".
Excel supplies these four functions for the four cases, returning the number of possible ways to "select r from n":
function (ex: pick 2 of 5) | result | order matters | repetition allowed |
PERMUTATIONA (5,2) | 25 | yes | yes |
PERMUT (5,2) | 20 | yes | no |
COMBINA (5,2) | 15 | no | yes |
COMBIN (5,2) | 10 | no | no |
A year ago (!) I put out a post on the Combinations Sheet of the Startup File. The challenge I put forward was to actually list the resulting selections. Only by visualizing the result can we understand the selection process; the number doesn't help. The sheet illustrates the process, (as shown below) and at the time I did not intend to take it any further.
Fast forward several months, and I was banging on the LAMBDA function, looking for applications. The idea of a function to return an array of selections from a set appealed to me. I set about it and accomplished the first and easiest one, permutations WITH repetition, using recursion. Several posts detailed my learning curve.
Again several months later, last week I returned to the challenge and presented the second solution, permutations WITHOUT repetition, and a new version of the first, using arrays in place of recursion.
NOW, I'm pleased to present the remaining two functions, combinations WITH and WITHOUT repetition. The last three functions are based on the original permutations function, reduced by removing selections that don't belong, from an input array of characters or symbols.
Arguments
The arguments required to calculate the number of selections, all four types, are two numbers: the number of items in the total population, and the number of items being selected. In the case of these custom LAMBDA functions, since the objective is array output, there must be array input. In the table below, yellow cells are numeric; green cells are arrays.
function | population | selection | output |
in math texts | n | r | number |
native Excel | number | number_chosen | number |
custom LAMBDA | from | pick | array |
from
This must be a 1-column array, either constant or formula. For example, digits can be entered as =SEQUENCE(10,,0), or as ={0;1;2;3;4;5;6;7;8;9}. An efficient method is to set up array constants in Name Manager for easy reference. Several examples are included in the demo file.
The items in the array must all have the same length. Normally they are single characters, such as letters, digits, symbols or some combination. Rare cases may require length more than one; for example, a deck of cards can be represented with two characters: ={"A♣";"2♣";"3♣"; ..."A♥";"2♥";"3♥"; ... etc.}. Multi-character items are handled in the logic but can get out of hand and should be avoided.
pick
This should be a small number. To demonstrate why, open a blank sheet and enter
=PERMUTATIONA(SEQUENCE(30),SEQUENCE(1,10))
Notice how quickly the number of output rows will exceed the rows available. The purpose of the array output functions is to expose the logical patterns of selection; returning a huge number of selections is not helpful. That's why they have an optional limit argument with a default limit of 10000. The Demo sheet has a validation limit of 5 on the pick cell.
One argument rule to note is that when repetition is allowed, you can pick more than the total number of items. For example, a coin has only two faces, but can be flipped an unlimited number of times. When repetition is not allowed, you cannot pick more than the total number of items.
Combination Logic
To shift gears from permutations to combinations, order no longer matters: "aab", "aba", and "baa" are all unique permutations, but are all the same combination of two "a" and one "b". We can thus step into this logic by listing permutations and counting the number of each item occurring in each one; concatenation of the counts then reveals duplicates. For example, if the "from" set is {"a";"b";"c"} then "aab," "aba," and "baa" all return the concatenated count "210".
The next trick is to include the first duplicate instance and exclude the rest. In this illustration sheet, value counts [V1] - [V9] (L:T) are concatenated in [Vall] (U), and duplicates (W) are identified using a dynamic OFFSET range to find "if this value is also found above it."
= IF( COUNTIF(
OFFSET( [@Vall], -1, 0, -(ROW() -ROW(Combinations[#Headers])), [@Vall]),1,"")
Thus, cell B17, permutation "21" has a Vall in U17 of 00011, which is the same as that of U13, permutation "12"; W17 is flagged as duplicate and the permutation is removed from the combination columns D and E. Clever enough, but this clearly won't do for an array function. On we go.
Below is the code and explanation of each new function:
Permutation Item Count (internal function)
Combinations WITH Repetition (output function)
Combinations WITHOUT Repetition (output function)
The functions that were presented last week are updated here:
Repetitions (internal function)
Permutations WITH Repetition (output function)
Permutations WITHOUT Repetition (output function)
Illustration
The sheet below shows the progression from permutations to combinations and from repetition to no repetition. Conditional highlighting and arrows show how one array is collapsed to another. Internal arrays (item counts and repeats) are shown for illustration. Each output array has a count above it, matching the respective native Excel function.
From Permutations WITH Repetition (c.perm.all) to WITHOUT Repetition (c.perm.nr)
From Permutations (c.perm.all) to Combinations (c.comb.all)
From Combinations WITH Repetition (c.comb.all) to WITHOUT Repetition (c.comb.nr)
More Examples
Binary Choice
Item Length > 1
Conclusion
There will be no rewards of fame and fortune from this work. Fortunately, that's not why I do what I do. I just love applying tools and ingenuity to a challenge, and making it easy for others to understand. Having a concrete objective like this affords me the opportunity to learn a lot while tackling each step. I've learned to integrate functions such as:
Programming and Logic: LAMBDA, LET, IF, IFERROR, NOT, OR, ISNUMBER
Math: PERMUTATIONA, MIN, MOD, ROUNDUP, SUM
Arrays: SEQUENCE, ROWS, BYROW, FILTER, UNIQUE, SORT, INDEX
Text: CONCAT, LEN, MID, FIND, TEXT, REPT
The four custom output functions together with the demo sheet are great for learning these math concepts as well as how to work with arrays and LAMBDA development. Visit the store to download the demo file FREE until Dec 31, 2022 using coupon code FREE4NOW.
Comments