Skip to content

Instantly share code, notes, and snippets.

@AoiYamada
Last active September 30, 2018 21:19
Show Gist options
  • Save AoiYamada/9c724a361d0ce157f51269bbe47a6bee to your computer and use it in GitHub Desktop.
Save AoiYamada/9c724a361d0ce157f51269bbe47a6bee to your computer and use it in GitHub Desktop.
Extend Array to support swap, combination, permutation... for general counting purpose
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