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