Welcome to a quick tutorial on permutations and combinations in Javascript. Ah, it’s that dreaded topic again. It has been donkey years, and people still put this confusing topic as an exercise in the school textbooks. To answer the permutations vs combinations question quickly:
- Permutations refer to:
- The number of ways we can arrange a list of things, and the order of things does matter.
- E.G. If we have
AB
, possible permutations areAB
andBA
. - I.E. “Singular”
A
is not a permutation ofAB
, because the order does matter andB
is missing.
- Combinations refer to:
- The number of variations we can create from a list of things, the order of things does not matter.
- E.G. If we have
AB
, possible combinations areA
,B
, andAB
. - I.E. The order does not matter, so
BA
is the same subset asAB
.
But in reality, permutations and combinations are actually not as commonly used… Nonetheless still pretty useful in security, analytics, and a piece of essential basic. So just what are permutations and combinations? What are the differences and how do they work in Javascript? Read on to find out!
TLDR – QUICK SLIDES
[web_stories_embed url=”https://code-boxx.com/web-stories/permutations-combinations/” title=”Permutations & Combinations” poster=”https://code-boxx.com/wp-content/uploads/2021/11/STORY-JS-20230518.webp” width=”360″ height=”600″ align=”center”]
Fullscreen Mode – Click Here
TABLE OF CONTENTS
PERMUTATIONS
All right, let us now go into permutations in this section.
WHAT ARE PERMUTATIONS?
Each of several possible ways in which a set or number of things can be ordered or arranged.
– Lexico
Yep, this definition should be very straightforward. Permutations are simply, “in how many ways can a list of things be arranged”.
A SIMPLE EXAMPLE
Maybe a simple example will illustrate permutations better. Let’s just say that we have 3 different fruits – Apple, banana, and coconut. So here are all the possible ways that we can arrange them:
First Item | Second Item | Third Item |
Apple | Banana | Coconut |
Apple | Coconut | Banana |
Banana | Apple | Coconut |
Banana | Coconut | Apple |
Coconut | Apple | Banana |
Coconut | Banana | Apple |
JAVASCRIPT PERMUTATION
Easy enough? But when it comes to actual implementation in Javascript, it does require quite a bit of trick up the sleeve.
function allPermutations (items) {
// allPermutations () : return a list of all possible permutations
// credits: https://stackoverflow.com/questions/9960908/permutations-in-javascript
let results = [];
function permute (arr, memo) {
var cur, memo = memo || [];
for (let i = 0; i < arr.length; i++) {
cur = arr.splice(i, 1);
if (arr.length === 0) {
results.push(memo.concat(cur));
}
permute(arr.slice(), memo.concat(cur));
arr.splice(i, 0, cur[0]);
}
return results;
}
permute(items);
return results;
}
var fruits = ["Apple", "Banana", "Coconut"];
var permutated = allPermutations(fruits);
console.table(permutated);
Not going to explain the script line-by-line here… You can do that in your own time. But in essence, we are simply using recursion to loop through the list of items and using flags to track all the possible permutations.
COMBINATIONS
Following up, we have combinations that are commonly confused with permutations.
WHAT ARE COMBINATIONS?
A combination is a selection of all or part of a set of objects, without regard to the order in which objects are selected.
This may sound very similar to permutations, but combinations refer to “how many variations we can get from a list of things”; It is referring to “how many different unique sets” and not “how many different arrangements”.
A SIMPLE EXAMPLE
Here is a simple example to better illustrate combinations, using the same old apple banana coconut as above:
First Item | Second Item | Third Item |
Apple | Banana | Coconut |
Apple | Banana | |
Apple | Coconut | |
Banana | Coconut | |
Apple | ||
Banana | ||
Coconut |
Yep, you can also think of combinations as all the possible subsets of a list of things. The order does not matter in combinations, because for example, banana apple is literally the same subset as apple banana.
JAVASCRIPT COMBINATIONS
function allCombinations (items) {
// allcombinations () : return a list of all possible combinations
let results = [];
for (let slots = items.length; slots > 0; slots--) {
for (let loop = 0; loop < items.length - slots + 1; loop++) {
let key = results.length;
results[key] = [];
for (let i = loop; i < loop + slots; i++) {
results[key].push(items[i]);
}
}
}
return results;
}
var fruits = ["Apple", "Banana", "Coconut"];
var combo = allCombinations(fruits);
console.table(combo);
Not going to go through line-by-line again… But this one should be a lot easier to understand without the use of recursion.
DOWNLOAD & NOTES
Here is the download link to the example code, so you don’t have to copy-paste everything.
SORRY FOR THE ADS...
But someone has to pay the bills, and sponsors are paying for it. I insist on not turning Code Boxx into a "paid scripts" business, and I don't "block people with Adblock". Every little bit of support helps.
Buy Me A Coffee Code Boxx eBooks
EXAMPLE CODE DOWNLOAD
Click here for the source code on GitHub gist, just click on “download zip” or do a git clone. I have released it under the MIT license, so feel free to build on top of it or use it in your own project.
EXTRA BITS & LINKS
That’s all for the tutorial, and here is a small section on some extras and links that may be useful to you.
EXTRA – PERMUTATIONS & COMBINATIONS WITH REPETITION
Please take note that the above examples are without repetitions. I.E. We only have one of each item. But even when repeated items are allowed, the basics remain the same. For example:
- Repeated permutations for ABC – AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBB, BBC, etc…
- Repeated combinations for ABC – ABC, AAA, BBB, CCC, AAB, AAC, BBC, BCC, AA, BB, CC, AB, AC, BC, A, B, C.
LINKS & REFERENCES
- K combination and permutation – rextester.com
- Permutations in JavaScript – Oleksii Trekhleb
- Combinations in Javascript – Oleksii Trekhleb
INFOGRAPHIC CHEATSHEET
THE END
Thank you for reading, and we have come to the end of this guide. I hope that it has helped you to better understand, and if you want to share anything with this guide, please feel free to comment below. Good luck and happy coding!
Helped me solve a problem, thanks! Could not find what I needed in other guides, but this was spot on.