Last active
May 31, 2023 17:59
-
-
Save kosson/a068c1173f795e282d07de77f87111f3 to your computer and use it in GitHub Desktop.
Searching for a very efficient solution for permutations on array elements in JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
let listOfArticles = ["HLP63P2I","HLP63P2I","R9T7FVD9","PLI82PFU","M62JFW8Q","W6FXWZHC","URVX9S22","UVF2BX3S","HH3R72BH","EUKZS3QR","PKRP3W4J","56YI28BH","WWZF8Z2V","YKEBAEX7","SB66FSJQ","HHJ739BB","VV26P2K9","ZZIDA78D","NWHASTVQ","RBLMDELC","BUEWZ258","3CQWK77M","WZBL4WV3","ZMPW6UQE","3APZQIYN","3XR95DME","C238ZP3G","PUIK8SYL","PQ7GP3G9","8EGSYTF4","SLEFYRWL","KVBLVJUU","YAPQI5C8","46NMCHCI","MBR34K6L","8K5HT8XM","WGLQYDYA","6MIN5N8G","9K6BU7U4","VWBWABD9","RWHZFBTC","GUBE5PM2","UCZZ7MFD","9T29K75C","J39EPBQU","44AFAI9W","JN8EEGB2"]; | |
console.log(listOfArticles.length); | |
/* == The functional programming solution == https://stackoverflow.com/questions/43241174/javascript-generating-all-combinations-of-elements-in-a-single-array-in-pairs == */ | |
let firstApproach = listOfArticles.flatMap( | |
(v, i) => listOfArticles.slice(i+1).map( w => v + ' ' + w ) | |
); | |
// console.log(firstApproach); | |
console.log(firstApproach.length); | |
/* === Second criptic solution (not suitable) === */ | |
const combinations = (arr) => [...Array(2 ** arr.length - 1).keys()].map((n) => ((n + 1) >>> 0).toString(2).split("").reverse().map((n, i) => (+n ? arr[i] : false)).filter(Boolean)).sort((a, b) => (a.length > b.length ? 1 : -1)); | |
console.log(combinations(["apple", "banana", "lemon", "mango"])); | |
/* === Third solution === */ | |
var results = []; | |
for (var i = 0; i < listOfArticles.length - 1; i++) { | |
// This is where you'll capture that last value | |
for (var j = i + 1; j < listOfArticles.length; j++) { | |
results.push(listOfArticles[i] + ' ' + listOfArticles[j]); | |
} | |
} | |
console.log(results); | |
function* generateDistinctPairs(array) { | |
for (let i = 0; i < array.length; i++) { | |
for (let j = i + 1; j < array.length; j++) { | |
yield [array[i], array[j]]; | |
} | |
} | |
}; | |
console.log(generateDistinctPairs(listOfArticles)) | |
// Another solution | |
const permutator = (inputArr) => { | |
let result = []; | |
const permute = (arr, m = []) => { | |
if (arr.length === 0) { | |
result.push(m) | |
} else { | |
for (let i = 0; i < arr.length; i++) { | |
let curr = arr.slice(); | |
let next = curr.splice(i, 1); | |
permute(curr.slice(), m.concat(next)) | |
} | |
} | |
} | |
permute(inputArr) | |
return result; | |
} | |
// source https://stackoverflow.com/questions/9960908/permutations-in-javascript/30013816#30013816 | |
// This looks very promissing | |
function* permute(permutation) { | |
var length = permutation.length, | |
c = Array(length).fill(0), | |
i = 1, k, p; | |
yield permutation.slice(); | |
while (i < length) { | |
if (c[i] < i) { | |
k = i % 2 && c[i]; | |
p = permutation[i]; | |
permutation[i] = permutation[k]; | |
permutation[k] = p; | |
++c[i]; | |
i = 1; | |
yield permutation.slice(); | |
} else { | |
c[i] = 0; | |
++i; | |
} | |
} | |
} | |
// Memory efficient iteration through permutations: | |
for (var permutation of permute([1, 2, 3])) console.log(permutation); | |
// Simple array conversion: | |
var permutations = [...permute([1, 2, 3])]; | |
// investigate!!! | |
/* | |
Documentation | |
https://stackoverflow.com/questions/43241174/javascript-generating-all-combinations-of-elements-in-a-single-array-in-pairs | |
Cool package: https://www.npmjs.com/package/js-combinatorics | |
Super cool proj: https://github.com/foo123/Abacus Explore!!! | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
For benchmarking: https://benchmarkjs.com/