'Generate All Permutations in Excel using LAMBDA
This is a frequently asked and answered question: how can I generate all permutations in Excel:
2011 2016 2017 2017 superuser 2018 2021
and now in 2022 which did not get an answer before it was closed as a duplicate, which is unfortunate because LAMBDA really changes the way that this question would be answered.
I have infrequently had the same need and get frustrated by having to reinvent a complex wheel. So, I will re-pose the question and put my own answer below. I will not mark any submissions as the answer, but invite good ideas. I am sure that my own approach can be improved upon.
Restating the 2022 question
I am trying to create a loop in excel with formulas only. What I am trying to achieve is described below. Let's say I have 3 columns as inputs: (i) Country; (ii) variable; and (iii) year. I want to expand from these inputs to then assign values to these parameters.
Inputs:
| Country | Variable | Year |
|---|---|---|
| GB | GDP | 2015 |
| DE | area | 2016 |
| CH | area | 2015 |
Outputs:
| Country | Variable | Year |
|---|---|---|
| GB | GDP | 2015 |
| GB | GDP | 2016 |
| GB | area | 2015 |
| GB | area | 2016 |
| DE | GDP | 2015 |
| DE | GDP | 2016 |
| DE | area | 2015 |
| DE | area | 2016 |
How can I do that efficiently using Excel?
Expanding the 2018 question
I have three columns, each of which has different kinds of master data as shown below:
Now, I want to have all possible combinations of these three cells - like
aa kk jj
aa kk ff
aa ll jj
aa ll ff
aa mm jj
...
Can this be done with a formula. I found one formula with 2 columns, but i'm not able to extend it to 3 columns correctly
Formula with 2 columns:
=IF(ROW()-ROW($G$1)+1>COUNTA($A$2:$A$15)*COUNTA($B$2:$B$4),"",
INDEX($A$2:$A$15,INT((ROW()-ROW($G$1))/COUNTA($B$2:$B$4)+1))&
INDEX($B$2:$B$4,MOD(ROW()-ROW($G$1),COUNTA($B$2:$B$4))+1))
where G1 is the cell to place the resulting value
Common Requirements
What these have in common is that they are both trying to create an ordered set of permutations from an ordered set of symbols. They both happen to need 3 levels of symbols, but the 2018 question was asking for help to go from 2 levels to 3 and the 2021 question was asking to go from 3 levels to 5. The 2022 question is just asking for 3 levels, but the output needs to be a table.
What if we go up to 6 levels like this?
| L1 | L2 | L3 | L4 | L5 | L6 |
|---|---|---|---|---|---|
| A | F | K | P | U | 1 |
| B | G | L | Q | V | 2 |
| C | H | R | W | 3 | |
| D | X | 4 | |||
| E |
This would generate 1'440 permutations.
| L1 | L2 | L3 | L4 | L5 | L6 |
|---|---|---|---|---|---|
| A | F | K | P | U | 1 |
| A | F | K | P | U | 2 |
| A | F | K | P | U | 3 |
| A | F | K | P | U | 4 |
| A | F | K | P | V | 1 |
| A | F | K | P | V | 2 |
| A | F | K | P | V | 3 |
| A | F | K | P | V | 4 |
| A | F | K | P | W | 1 |
| ... | ... | ... | ... | ... | ... |
Making a general formula that takes in any number of levels (columns) is hard. Just go through the answers provided - they each required some rocket science and until now, all the solutions had hard-coded limits on the number of columns of symbols. So can LAMBDA give us a general solution?
Solution 1:[1]
Cool question and brain teezer; I just puzzled on something which is using MAKEARRAY():
Option 1:
What you'd call as "super inefficient" is creating a list of permutations when you calculate rows^columns. I think the following is not that inefficient. Let's imagine the following:
Formula in E1:
=LET(A,A1:C3,B,ROWS(A),C,COLUMNS(A),D,B^C,E,UNIQUE(MAKEARRAY(D,C,LAMBDA(rw,cl,INDEX(IF(A="","",A),MOD(CEILING(rw/(D/(B^cl)),1)-1,B)+1,cl)))),FILTER(E,MMULT(--(E<>""),SEQUENCE(C,,,0))=C))
In short, what this does:
- Variables A-D are all helpers.
- The idea then is to just use simple
INDEX()s to return all values. To do so we need the right indices for both rows and columns. MAKEARRAY()will make calculations relatively easy due to the recursive functionality that lambda brings. Inside these functions its basic math to return the correct indices for both these rows and columns. In fact there is no calculation needed for the columns as we simply refer to 'cl' and all the calculation for all the row indices is done throughMOD(CEILING(rw/(D/(B^cl)),1)-1,B)+1.- The result from the above is put into
UNIQUE()to use very little resources to filter out any potential duplicates and limit potential empty rows to just a single empty row. FILTER()andMMULT()work nicely together to filter out any unwanted results (read; empty).
That's as compact and quick as I think I could get this. The formula will now work on any contiguous range of cells. A single cell, a single row, a single column or any 2D-range.
Option 2:
OP rightfully mentioned that option 1 could create too many tuples at the start to only later discard them. This can be inefficient. To tackle this issue (and if this is not something you want), we can use a much larger formula. Let's imagine the following data:
| A | B | C |
|---|---|---|
| a | d | f |
| b | e | h |
| e | ||
| c | g | |
| g |
We see that there are empty cells and duplicate values. These are the reasons option 1 would create too many tuples. To counter that I came up with a much longer formula:
=LET(A,A1:C5,B,ROWS(A),C,COLUMNS(A),D,IF(A="",NA(),A),E,MAKEARRAY(B,C,LAMBDA(rw,cl,INDEX(SORT(INDEX(D,0,cl)),rw))),F,BYCOL(E,LAMBDA(cl,COUNTA(FILTER(cl,NOT(ISERROR(cl)))))),G,MAKEARRAY(PRODUCT(F),C,LAMBDA(rw,cl,INDEX(E,MOD(CEILING(rw/IFERROR(PRODUCT(INDEX(F,SEQUENCE(C-cl,,cl+1))),1),1)-1,INDEX(F,cl))+1,cl))),UNIQUE(G))
To break this down:
LET()- Work with variables;A- Our initial full range of cells (contiguous);B- The total amount of rows of A;C- The total amount of columns of A;D- The formulaIF(A="",NA(),A)is meant to check each value in the matrix if it's empty (string). If so, make it an error (which will make sense in the next step).E- In this step the formulaMAKEARRAY(B,C,LAMBDA(rw,cl,INDEX(SORT(INDEX(D,0,cl)),rw)))is sorting each column so the values are on top and all errors pushed down:
| A | B | C |
|---|---|---|
| a | d | f |
| b | e | g |
| c | e | g |
| #N/A | #N/A | h |
| #N/A | #N/A | #N/A |
F- This variable's formulaBYCOL(E,LAMBDA(cl,COUNTA(FILTER(cl,NOT(ISERROR(cl))))))will now count the amount of items per columns. This is needed for later use and to count all permutations. The outcome in this specific case would be{3;3;4}.G- The last variable (if one chooses to use it as such) usingMAKEARRAY(PRODUCT(F),C,LAMBDA(rw,cl,INDEX(E,MOD(CEILING(rw/IFERROR(PRODUCT(INDEX(F,SEQUENCE(C-cl,,cl+1))),1),1)-1,INDEX(F,cl))+1,cl))). It's rather long but each step makes sense; Get the product (all possible permutations) to calculate the total amount of rows, the columns stay the same. In theLAMBDA()we refer to all columns after the current column-indice in theFvariable. It's quite a big chunk to digest and unfortunately I'm not good enough in explaining =).UNIQUE(G)- The very last step is to filter out all double permutations if one chooses too.
The result:
Now, even though option 1 would beat option 2 in readability, the 2nd option took (with very limited testing) just a third of the time it took the 1st option to calculate. So in terms of speed, this 2nd option would be preferred.
As an alternative to the 2nd option I first had:
=LET(A,A1:C5,B,ROWS(A),C,COLUMNS(A),D,MAKEARRAY(B,C,LAMBDA(rw,cl,IF(MATCH(INDEX(A,rw,cl),INDEX(A,0,cl),0)=rw,INDEX(A,rw,cl),NA()))),E,MAKEARRAY(B,C,LAMBDA(rw,cl,INDEX(SORT(INDEX(D,0,cl)),rw))),F,BYCOL(E,LAMBDA(cl,COUNTA(UNIQUE(FILTER(cl,NOT(ISERROR(cl))))))),G,MAKEARRAY(PRODUCT(F),C,LAMBDA(rw,cl,INDEX(E,MOD(CEILING(rw/IFERROR(PRODUCT(INDEX(F,SEQUENCE(C-cl,,cl+1))),1),1)-1,INDEX(F,cl))+1,cl))),G)
This would now change the D variable to a longer formula to remove duplicates in each column beforehand. Both variations would work just fine.
Solution 2:[2]
A Simple LET supported by LAMBDA
To the 2022 question, I used the following LET:
=LET( matrix, A2:E6,
cC, COLUMNS( matrix ), cSeq, SEQUENCE( 1, cC ),
rC, ROWS( matrix ), rSeq, SEQUENCE( rC ),
eC, rC ^ cC, eSeq, SEQUENCE( eC,,0 ),
unblank, IF( ISBLANK(matrix), "°|°", matrix ),
m, UNIQUE( INDEX( unblank, MOD( INT( INT( SEQUENCE( eC, cC, 0 )/cC )/rC^SEQUENCE( 1, cC, cC-1, -1 ) ), rC ) + 1, cSeq ) ),
FILTER( m, BYROW( IFERROR( FIND( "°|°", m ), 0 ), LAMBDA(x, SUM( x ) ) ) = 0 ) )
where the matrix that is used to generate the permutations in in A2:E6:
This formula inserts "°|°" in place of blanks so as to avoid having the blanks recast as 0's. It eliminates duplicates by applying UNIQUE.
This is super inefficient because it generates every possible permutation, including repeats and then filters them out. For a small scale matrix, it's not a big deal, but imagine that a 100 row by 3 column matrix would generate 1'000'000 rows and then filter them down to a small subset.
There is one small benefit, however, notice the f in the yellow cell, stranded in the middle of the column and not contiguous with its peers. This formula handles that like a champ. It just integrates it into the outputs of valid permutations. That will be important in the efficient formula below.
An Efficient General LET supported by LAMBDA
As for a general LAMBDA formula, I used:
SYMBOLPERMUTATIONS =
LAMBDA( matrix,
LET(
cC, COLUMNS( matrix ),
cSeq, SEQUENCE( 1, cC ),
symbolCounts, BYCOL( matrix, LAMBDA(x, SUM( --NOT( ISBLANK( x ) ) ) ) ),
rSeq, SEQUENCE( MAX( symbolCounts )-1 ),
permFactors, INDEX( SCAN( 1, INDEX( symbolCounts, , cC-cSeq+1), LAMBDA(a,b, a*b ) ),, cC-cSeq+1 ),
permMods, IFERROR( INDEX( permFactors,, IF( cSeq + 1 > cC, -1, cSeq+1 ) ), 1 ),
idx, INT( MOD( SEQUENCE( INDEX(permFactors, 1, 1),,0 ), permFactors )/permMods ) + 1,
answer, INDEX( matrix, idx, cSeq ),
er, OR( BYCOL( --ISBLANK(matrix), LAMBDA(x, SUM(--(INDEX(x,rSeq+1)<INDEX(x,rSeq))) ) ) ), // detect if there are stranded symbols
IF( SUM(symbolCounts)=0, "no symbols",
IF( er, "symbol columns must be contiguous",
answer ) ) )
)
This takes in matrix, just as above (the LET version is shown below). It delivers quite the same result, but there are significant differences:
- It is efficient. In the example shown here, the Simple formula
above would generate
5^6 = 15625permutations just to arrive at1440valid ones. This generates only what is needed and does not require filtering. - However, it does not handle that stranded f at all. In fact, it would generate a 0 in the place of the f which is not something that a user with a ton of permutations might even notice.
For this reason, there is error detection and handling. The variable er detects if there are any stranded symbols in the matrix that are not column-wise contiguous with the ones above it using this LAMBDA Helper:
OR( BYCOL( --ISBLANK(matrix), LAMBDA(x, SUM(--(INDEX(x,rSeq+1)<INDEX(x,rSeq))) ) ) )
But this creates a new challenge and perhaps a whole new question. In the case of the stranded f, can anyone come up with a way to incorporate it?
The other error trap is to detect if the column is completely empty.
LAMBDA Magic
The magic that LAMBDA brings is from this one line that makes both formulas extensible to any number of columns without having to hard code them:
permFactors, INDEX( SCAN( 1, INDEX( symbolCounts, , cC-cSeq+1), LAMBDA(a,b, a*b ) ),, cC-cSeq+1 )
I got this from JvdV's answer to this question that was aimed specifically at trying to solve this question. Scott Craner & Bosco Yip had showed that it was basically unsolvable without LAMBDA and JvdV showed how it can be done with the LAMBDA helper SCAN.
LET Version of the Efficient Formula
=LET( matrix, A2:F6,
cC, COLUMNS( matrix ),
cSeq, SEQUENCE( 1, cC ),
symbolCounts, BYCOL( matrix, LAMBDA(x, SUM( --NOT( ISBLANK( x ) ) ) ) ),
rSeq, SEQUENCE( MAX( symbolCounts )-1 ),
permFactors, INDEX( SCAN( 1, INDEX( symbolCounts, , cC-cSeq+1), LAMBDA(a,b, a*b ) ),, cC-cSeq+1 ),
permMods, IFERROR( INDEX( permFactors,, IF( cSeq + 1 > cC, -1, cSeq+1 ) ), 1 ),
idx, INT( MOD( SEQUENCE( INDEX(permFactors, 1, 1),,0 ), permFactors )/permMods ) + 1,
answer, INDEX( matrix, idx, cSeq ),
er, OR( BYCOL( --ISBLANK(matrix), LAMBDA(x, SUM(--(INDEX(x,rSeq+1)<INDEX(x,rSeq))) ) ) ),
IF( SUM(symbolCounts)=0, "no symbols",
IF( er, "symbol columns must be contiguous",
answer ) ) )
Solution 3:[3]
Perhaps an iterative LAMBDA:
MyLambda defined in Name Manager as:
=LAMBDA(n,
LET(
Rng, Sheet1!$A$1:$D$3,
?, COLUMNS(Rng),
?, INDEX(Rng, , n),
?, FILTER(?, ? <> ""),
IF( n > ?,
"",
LET(?, ? & REPT(CHAR(32), 25) & TRANSPOSE(MyLambda(n + 1)),
?, COLUMNS(?),
?, SEQUENCE(ROWS(?) * ?, , 0),
INDEX(?, 1 + QUOTIENT(?, ?), 1 + MOD(?, ?))
)
)
)
)
after which we can then call
=LET(Rng,Sheet1!$A$1:$D$3,?,COLUMNS(Rng),TRIM(MID(MyLambda(1),25*SEQUENCE(,?,0)+1,25)))
within the worksheet.
Note that each column within Rng must contain at least one entry
The logic behind the LAMBDA is to iteratively (via the call to MyLambda(n+1) within MyLambda) concatenate successive columns within the range, based on the fact that the concatenation of two orthogonal arrays generates a two-dimensional array comprising all permutations of elements of those two arrays.
={"Dave";"Mike"}&TRANSPOSE({"Bob";"Steve";"Paul"})
for example, generates
{"DaveBob","DaveSteve","DavePaul";"MikeBob","MikeSteve","MikePaul"}
which then needs to be redimensioned to a one-dimensional horizontal array, i.e.
{"DaveBob";"DaveSteve";"DavePaul";"MikeBob";"MikeSteve";"MikePaul"}
such that it can be iteratively concatenated with the next (vertical, orthogonal) column within the range. And so on.
We are effectively:
unpivoting: {"Bob","Steve","Paul";"Bob","Steve","Paul";"Bob","Steve","Paul"} by: {"Dave";"Mike"}So the input array n is:
| A | B |
|---|---|
| Dave | Bob |
| Mike | Steve |
| Paul |
Column B gets transposed and replicated:
| A | B | C | D |
|---|---|---|---|
| Dave | Bob | Steve | Paul |
| Mike | Bob | Steve | Paul |
and now we UNPIVOT (a kind of flatten) Columns B, C & D by Column A:
| A | B |
|---|---|
| Dave | Bob |
| Dave | Steve |
| Dave | Paul |
| Mike | Bob |
| Mike | Steve |
| Mike | Paul |
NOTE: This approach:
- efficiently generates all permutations without repetition
- ignores blanks and does not require symbols to be on adjacent rows
The second function, called within the worksheet, then parses the concatenated array into the required number of rows/columns.
Solution 4:[4]
There are problems with my previous answer(s):
- The Simple formula ignores blanks and does not require symbols be on adjacent rows in the same column, but is inefficient. If given an array with 100 rows in column A, and 3 in column B and 2 in column C, the result should be
100 x 3 x 2 = 600, but it will instead generate100 x 100 x 100 = 1'000'000and then filter them. That takes more than 2 minutes to calculate! It also blows up if any column in the input array is completely blank. - The Efficient General LET is fast and does not waste computation, but it cannot handle inputs with symbols on non-adjacent rows (the stranded f) and will also blow up if any column is completely blank.
Insights from Jos Woolley's Solution
The solution by Jos Woolley offers two insights that allow for an efficient solution that does not have the problems of either of my previous approaches:
- the objective is actually to break up each column and successively unpivot it by the next column
- this idea can be implemented through LAMBDA recursion
Recursive LAMBDA Solution
With these insights, I am able to propose an efficient LAMBDA solution. The following is fully commented so that you can paste it directly into your Advanced Formula Editor:
PERMUTATEARRAY =
/* This function recursively generates all unique permutations of an ordered array of symbols.
It is efficient - i.e., it does not generate duplicate rows that require filtering.
The arguments are:
symbolArray - ia a required array input (unless the recursion is done).
Is an array of ordered symbols where the left most column contains symbols that will be permutated
by the permutation of the symbols in the next columns to the right. e.g.,
with symbolArray of:
A 1
B 2
A and B will be permutated by 1 and 2:
A 1
A 2
B 1
B 2
byArray - optional array that will be used to permutate the next column of the symbolArray.
This is passed between recursions and it not intended for use by the user but it can be used.
cleaned - optional argument to indicate that the symbolArray has already been cleaned.
This prevents the function from repeatedly cleaning the symbolArray that would otherwise require
a repetition for each column of the symbolArray. It is passed between recursions and it not
intended for use by the user but can be used.
Example - With a symbolArray of:
A C 1
B D 2
The output would be the following array:
A C 1
A C 2
A D 1
A D 2
B C 1
B C 2
B D 1
B D 2
NOTES:
- Blanks will be ignored.
- errors will be ignored. (see comments below to change this)
- all rows of the resulting array will be unique
- blank columns in the symbol array are removed
- this function has no dependencies on external LAMBDA functions even though that would make it more
readable.
------------------------------------ */
LAMBDA( symbolArray, [byArray], [cleaned],
IF( AND(ISOMITTED(symbolArray),ISOMITTED(byArray)), ERROR.TYPE(7), // DONE
IF(ISOMITTED(symbolArray), byArray, // if there is no symbolArray, the function is DONE.
LET(
clnSymArray, IF(ISOMITTED(cleaned), //If the symbol array has not been cleaned, then clean it.
/* Only clean arrays can be permuated. They cannot contain blanks because those are interpreted as 0's.
The input also cannot contain entirely blank columns, so these are removed.
The input cells also cannot contain errors as this will cause the whole function to error. That,
however, is a design choice. They are filtered out inside of this function because the user cannot
easily filter them out before passing them as arguments - IFERROR(x,"") causes all blanks to become 0's.
*/
LET(
COMPRESSC, LAMBDA( a,
FILTER(a,BYCOL(a,LAMBDA(a,SUM(--(a<>""))>0)))
),
REPLBLANKS, LAMBDA(array, [with],
LET(w, IF(ISOMITTED(with), "", with),
IF(array = "", w, array)
)
),
REPLERRORS, LAMBDA(array, [with],
LET(w, IF(ISOMITTED(with), "", with),
IFERROR(array, w)
)
),
COMPRESSC( REPLERRORS( REPLBLANKS(symbolArray) ) )
// COMPRESSC( REPLBLANKS(symbolArray) ) //removes the REPLERRORS if the user wants errors to result in erroring the function.
),
symbolArray ), //otherwise, pass the symbolArray
//Once cleaned, effectively execute PERMUTATEARRAY( clnSymArray, byArray, 1 )
IF( AND(COLUMNS( clnSymArray ) = 1, ISOMITTED( byArray ) ),
UNIQUE(FILTER(clnSymArray,clnSymArray<>"")), /* if the user gives a single column, give it back clean even if it was already cleaned.
there is no point in testing again whether Clean has been set. DONE */
/* Otherwise, we can recursively process the inputs in the following LET. */
LET(
// MUX is an internal LAMBDA function that permutates the left most column of the p array by the b (by) array.
MUX, LAMBDA( p, b,
LET(pR, ROWS( p ),
byR, ROWS( b ),
byC, COLUMNS( b ),
byCseq, SEQUENCE(,byC+1), // forces this to look at only one column of p
oRSeq, SEQUENCE( byR * pR,,0 ),
IFERROR( INDEX( b, oRSeq/pR+1, byCseq),
INDEX( p, MOD(oRSeq,pR )+1, byCseq-byC ) )
)
),
pRSeq, SEQUENCE(ROWS(clnSymArray)),
// Decide when to apply MUX versus when to recurse. MUX is always the final output.
// if there are only two symbol columns with no byArray, filter & MUX the two columns - DONE
IF( AND(COLUMNS( clnSymArray ) = 2, ISOMITTED( ByArray ) ),
LET(pFin, INDEX( clnSymArray, pRSeq, 2),
fpFin, UNIQUE(FILTER(pFin,pFin<>"")),
bFin, INDEX( clnSymArray, pRSeq, 1),
fbFin, UNIQUE(FILTER(bFin,bFin<>"")),
MUX( fpFin, fbFin )
),
// if there are more than two symbol columns with no byArray, repartition the symbol and byArray and recurse
IF( AND(COLUMNS( clnSymArray ) > 2, ISOMITTED( ByArray ) ),
LET(pC, COLUMNS(clnSymArray),
pCSeq, SEQUENCE(,pC-2,3),
pNext, INDEX( clnSymArray, pRSeq, pCSeq ),
pFin, INDEX( clnSymArray, pRSeq, 2),
fpFin, UNIQUE(FILTER(pFin,pFin<>"")),
bFin, INDEX( clnSymArray, pRSeq, 1),
fbFin, UNIQUE(FILTER(bFin,bFin<>"")),
bNext, MUX( fpFin, fbFin ),
PERMUTATEARRAY( pNext, bNext, 1 )
) ,
// if there is more than one symbol column and a byArray, repartition the symbol and byArray and recurse
IF( AND(COLUMNS( clnSymArray ) > 1, NOT( ISOMITTED( ByArray ) ) ),
LET(pC, COLUMNS(clnSymArray),
pCSeq, SEQUENCE(,pC-1,2),
pNext, INDEX( clnSymArray, pRSeq, pCSeq ),
pFin, INDEX( clnSymArray, pRSeq, 1),
fpFin, UNIQUE(FILTER(pFin,pFin<>"")),
bNext, MUX( fpFin, ByArray ),
PERMUTATEARRAY( pNext, bNext, 1 )
),
// if there is only one symbol column and a byArray, filter symbol column & MUX it with he byArray - DONE
IF( AND(COLUMNS( clnSymArray ) = 1, NOT( ISOMITTED( ByArray ) ) ),
LET(pFin, INDEX( clnSymArray, pRSeq, 1),
fpFin, UNIQUE(FILTER(pFin,pFin<>"")),
MUX( fpFin, ByArray )
)
)
) ) )
) ) )
)
)
);
Even if you remove the comments, there is a lot of code in here, but it is designed that way in order to maximize speed while preventing errors. It is also a fully contained LAMBDA, meaning that it does not need any other LAMBDA functions to be loaded in order to work.
It is able to handle symbols in non-adjacent rows from the same column (the stranded f problem), completely blank columns, and errors in the input array. Here is an example that has all of those problems:
LAMBDA Magic --> Turing Complete
In my previous answer, I could see that LAMBDA allows us now to have an extensible solution to this problem thanks to the use of LAMBDA Helpers as JvdV has shown with a running permutation using SCAN(array,LAMBDA(a,b,a*b)).
Now, LAMBDA allows for recursion and looping that are even more powerful for this particular problem. Without Jos's insight, I would not have recognized that there is a repeating recursive pattern. This new solution may be lengthy, but it solves the problem in a more computationally efficient way which would prevent the spreadsheet from becoming unnecessarily laggy.
On the downside, debugging recursion is a huge pain!
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | |
| Solution 2 | |
| Solution 3 | mark fitzpatrick |
| Solution 4 | mark fitzpatrick |