Skip to content

Instantly share code, notes, and snippets.

@primaryobjects
Last active February 12, 2017 14:49
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save primaryobjects/0529ee9e01ea4e3a264a1bc1ec37f969 to your computer and use it in GitHub Desktop.
Combinations and permutations in Javascript. Demo at http://jsbin.com/xufomalori/edit?js,console
// Combinations and permutations.
// Counts can be verified at http://www.calculatorsoup.com/calculators/discretemathematics/permutations.php
// noprotect
var combinations = function(arr) {
var result = [];
for (var i=0; i<arr.length; i++) {
var item1 = arr[i];
for (var j=i+1; j<arr.length; j++) {
var item2 = arr[j];
result.push([item1, item2]);
}
}
return result;
}
var permutations = function(arr) {
var result = [];
for (var i=0; i<arr.length; i++) {
var item1 = arr[i];
for (var j=0; j<arr.length; j++) {
var item2 = arr[j];
if (item1 !== item2) {
result.push([item1, item2]);
}
}
}
return result;
}
var combinationsn = function(arr, n) {
var result = [];
var indexes = [];
for (var i=0; i<n; i++) {
indexes.push(i);
}
var i=0;
while (i < arr.length) {
var items = [];
for (var j=0; j<indexes.length; j++) {
var index = indexes[j];
items.push(arr[index]);
}
var idx = indexes.length - 1;
var lastIndex = indexes[idx];
while (lastIndex == arr.length - 1 && idx > 0) {
idx--;
lastIndex = indexes[idx];
}
if (indexes[idx] < arr.length - 1) {
indexes[idx]++;
var count = 0;
for (var k=idx + 1; k<indexes.length; k++) {
indexes[k] = indexes[idx + count] + 1;
if (indexes[k] >= arr.length) {
indexes[k] = arr.length - 1;
}
count++;
}
i = 0;
}
var skip = false;
for (var k=0; k<items.length - 1; k++) {
for (var l=k+1; l<items.length; l++) {
if (items[k] === items[l]) {
skip = true;
break;
}
}
}
if (n == 1) {
for (var k=0; k<result.length; k++) {
if (result[k][0] === items[0]) {
skip = true;
break;
}
}
}
if (!skip) {
result.push(items);
}
i++;
}
return result;
}
var permutationsn = function(arr, n) {
var result = [];
var indexes = [];
for (var i=0; i<n; i++) {
indexes.push(i);
}
var i=0;
while (i < arr.length) {
var items = [];
for (var j=0; j<indexes.length; j++) {
var index = indexes[j];
items.push(arr[index]);
}
var idx = indexes.length - 1;
var lastIndex = indexes[idx];
while (lastIndex == arr.length - 1 && idx > 0) {
idx--;
lastIndex = indexes[idx];
}
if (indexes[idx] < arr.length - 1) {
indexes[idx]++;
for (var k=idx + 1; k<indexes.length; k++) {
indexes[k] = 0;
}
i = 0;
}
var skip = false;
for (var k=0; k<items.length - 1; k++) {
for (var l=k+1; l<items.length; l++) {
if (items[k] === items[l]) {
skip = true;
break;
}
}
}
if (n == 1) {
for (var k=0; k<result.length; k++) {
if (result[k][0] === items[0]) {
skip = true;
break;
}
}
}
if (!skip) {
result.push(items);
}
i++;
}
return result;
}
var factorial = function(n) {
var result = 1;
for (var i=n; i>0; i--) {
result *= i;
}
return result;
}
var combinationCount = function(n, k) {
var result = 1;
var divisor = (factorial(k) * factorial(n - k));
if (divisor) {
result = factorial(n) / divisor;
}
return result;
}
var permutationCount = function(n, k) {
var result = 1;
var divisor = factorial(n - k);
if (divisor) {
result = factorial(n) / divisor;
}
return result;
}
var list = ['x','y','a','b','c','d','e','f'];
var c = combinations(list);
console.log(c.length + ' combinations.');
console.log(c);
var p = permutations(list);
console.log(p.length + ' permutations.');
console.log(p);
for (var i=1; i<=list.length; i++) {
console.log(combinationsn(list, i).length == combinationCount(list.length, i));
}
for (var i=1; i<=list.length; i++) {
console.log(permutationsn(list, i).length == permutationCount(list.length, i));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment