Last active
September 30, 2018 21:19
-
-
Save AoiYamada/9c724a361d0ce157f51269bbe47a6bee to your computer and use it in GitHub Desktop.
Extend Array to support swap, combination, permutation... for general counting purpose
This file contains hidden or 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
class Counting extends Array { | |
constructor(...items) { | |
if (items.length > 1) super(...items); | |
else { | |
super(); | |
this.push(...items); | |
} | |
} | |
swap(idx1, idx2) { | |
const length = this.length; | |
if (idx1 >= length || idx2 > length) | |
throw new Error("Index Greater than length"); | |
[this[idx1], this[idx2]] = [this[idx2], this[idx1]]; | |
} | |
combination(k = this.length, array = this) { | |
const max = array.length; | |
const combinations = []; | |
if (!(k <= 0 || k > max || !max)) { | |
combinator([], array); | |
} | |
function combinator(temp, rest) { | |
if (temp.length < k) { | |
const rl = rest.length; | |
for (let idx = 0; idx < rl && max - idx >= k; idx++) { | |
combinator([...temp, rest[idx]], rest.slice(idx + 1)); | |
} | |
} else { | |
combinations.push(temp); | |
} | |
} | |
return combinations; | |
} | |
permutation(k = this.length, array = this) { | |
// Heaps Algorithm | |
// https://stackoverflow.com/questions/27539223/permutations-via-heaps-algorithm-with-a-mystery-comma | |
let tempArray = []; | |
const permutations = []; | |
const combinations = this.combination(k, array); | |
for (const combination of combinations) { | |
tempArray = combination; | |
permutator(k); | |
} | |
function permutator(size) { | |
if (size === 1) { | |
permutations.push([...tempArray]); | |
} else { | |
for (var i = 0; i < size; i++) { | |
permutator(size - 1); | |
swap(size % 2 ? 0 : i, size - 1); | |
} | |
} | |
} | |
function swap(idx1, idx2) { | |
[tempArray[idx1], tempArray[idx2]] = [ | |
tempArray[idx2], | |
tempArray[idx1], | |
]; | |
} | |
return permutations; | |
} | |
static deepPermutation(...arrays) { | |
const countings = new Counting(...arrays); | |
const orders = countings.permutation(); | |
const permutations = []; | |
for (const order of orders) { | |
permutations.push(...Counting.deepCombination(...order)); | |
} | |
return permutations; | |
} | |
static deepCombination(...arrays) { | |
const max = arrays.length; | |
const combinations = []; | |
function combinator(temp = [], array = arrays[0]) { | |
const idx = temp.length; | |
if (temp.length < max) | |
for (const element of array) { | |
combinator([...temp, element], arrays[idx + 1]); | |
} | |
else combinations.push(temp); | |
} | |
combinator(); | |
return combinations; | |
} | |
static factorial(n) { | |
if (n < 0 || n > Counting.MAX_SAFE_FACTOIAL || n != ~~n) | |
throw new Error(`Expect n to be an integer between 0 to ${Counting.MAX_SAFE_FACTOIAL} inclusively, but recieve ${n}`); | |
return Counting.FACTORIAL_ARRAY[n]; | |
} | |
static P(n, r) { | |
return Counting.factorial(n) / Counting.factorial(n - r); | |
} | |
static C(n, r) { | |
return Counting.P(n, r) / Counting.factorial(r); | |
} | |
} | |
Counting.FACTORIAL_ARRAY = [ | |
1, | |
1, | |
2, | |
6, | |
24, | |
120, | |
720, | |
5040, | |
40320, | |
362880, | |
3628800, | |
39916800, | |
479001600, | |
6227020800, | |
87178291200, | |
1307674368000, | |
20922789888000, | |
355687428096000, | |
6402373705728000 | |
]; | |
Counting.MAX_SAFE_FACTOIAL = Counting.FACTORIAL_ARRAY.length - 1; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment