Menu
Programming by permutation, sometimes called "programming by accident" or "shotgunning", is an approach to software development wherein a programming problem is solved by iteratively making small changes (permutations) and testing each change to see if it behaves as desired.
You take first element of an array (k=0) and exchange it with any element (i) of the array. Then you recursively apply permutation on array starting with second element. This way you get all permutations starting with i-th element.
A Permutation of a string is another string that contains same characters, only the order of characters can be different. For example, “abcd” and “dabc” are Permutation of each other.
Little late, but like to add a slightly more elegant version here. Can be any array...
function permutator(inputArr) {
var results = [];
function permute(arr, memo) {
var cur, memo = memo || [];
for (var i = 0; i < arr.length; i++) {
cur = arr.splice(i, 1);
if (arr.length === 0) {
results.push(memo.concat(cur));
}
permute(arr.slice(), memo.concat(cur));
arr.splice(i, 0, cur[0]);
}
return results;
}
return permute(inputArr);
}
Adding an ES6 (2015) version. Also does not mutate the original input array. Works in the console in Chrome...
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;
}
So...
permutator(['c','a','t']);
Yields...
[ [ 'c', 'a', 't' ],
[ 'c', 't', 'a' ],
[ 'a', 'c', 't' ],
[ 'a', 't', 'c' ],
[ 't', 'c', 'a' ],
[ 't', 'a', 'c' ] ]
And...
permutator([1,2,3]);
Yields...
[ [ 1, 2, 3 ],
[ 1, 3, 2 ],
[ 2, 1, 3 ],
[ 2, 3, 1 ],
[ 3, 1, 2 ],
[ 3, 2, 1 ] ]
If you notice, the code actually splits the chars into an array prior to do any permutation, so you simply remove the join and split operation
var permArr = [],
usedChars = [];
function permute(input) {
var i, ch;
for (i = 0; i < input.length; i++) {
ch = input.splice(i, 1)[0];
usedChars.push(ch);
if (input.length == 0) {
permArr.push(usedChars.slice());
}
permute(input);
input.splice(i, 0, ch);
usedChars.pop();
}
return permArr
};
document.write(JSON.stringify(permute([5, 3, 7, 1])));The following very efficient algorithm uses Heap's method to generate all permutations of N elements with runtime complexity in O(N!):
function permute(permutation) {
var length = permutation.length,
result = [permutation.slice()],
c = new Array(length).fill(0),
i = 1, k, p;
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;
result.push(permutation.slice());
} else {
c[i] = 0;
++i;
}
}
return result;
}
console.log(permute([1, 2, 3]));The same algorithm implemented as a generator with space complexity in O(N):
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])];Feel free to add your implementation to the following benchmark.js test suite:
function permute_SiGanteng(input) {
var permArr = [],
usedChars = [];
function permute(input) {
var i, ch;
for (i = 0; i < input.length; i++) {
ch = input.splice(i, 1)[0];
usedChars.push(ch);
if (input.length == 0) {
permArr.push(usedChars.slice());
}
permute(input);
input.splice(i, 0, ch);
usedChars.pop();
}
return permArr
}
return permute(input);
}
function permute_delimited(inputArr) {
var results = [];
function permute(arr, memo) {
var cur, memo = memo || [];
for (var i = 0; i < arr.length; i++) {
cur = arr.splice(i, 1);
if (arr.length === 0) {
results.push(memo.concat(cur));
}
permute(arr.slice(), memo.concat(cur));
arr.splice(i, 0, cur[0]);
}
return results;
}
return permute(inputArr);
}
function permute_monkey(inputArray) {
return inputArray.reduce(function permute(res, item, key, arr) {
return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) {
return [item].concat(perm);
}) || item);
}, []);
}
function permute_Oriol(input) {
var permArr = [],
usedChars = [];
return (function main() {
for (var i = 0; i < input.length; i++) {
var ch = input.splice(i, 1)[0];
usedChars.push(ch);
if (input.length == 0) {
permArr.push(usedChars.slice());
}
main();
input.splice(i, 0, ch);
usedChars.pop();
}
return permArr;
})();
}
function permute_MarkusT(input) {
function permutate(array, callback) {
function p(array, index, callback) {
function swap(a, i1, i2) {
var t = a[i1];
a[i1] = a[i2];
a[i2] = t;
}
if (index == array.length - 1) {
callback(array);
return 1;
} else {
var count = p(array, index + 1, callback);
for (var i = index + 1; i < array.length; i++) {
swap(array, i, index);
count += p(array, index + 1, callback);
swap(array, i, index);
}
return count;
}
}
if (!array || array.length == 0) {
return 0;
}
return p(array, 0, callback);
}
var result = [];
permutate(input, function(a) {
result.push(a.slice(0));
});
return result;
}
function permute_le_m(permutation) {
var length = permutation.length,
result = [permutation.slice()],
c = new Array(length).fill(0),
i = 1, k, p;
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;
result.push(permutation.slice());
} else {
c[i] = 0;
++i;
}
}
return result;
}
function permute_Urielzen(arr) {
var finalArr = [];
var iterator = function (arrayTaken, tree) {
for (var i = 0; i < tree; i++) {
var temp = arrayTaken.slice();
temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]);
if (tree >= arr.length) {
finalArr.push(temp);
} else { iterator(temp, tree + 1); }
}
}
iterator(arr, 1); return finalArr;
}
function permute_Taylor_Hakes(arr) {
var permutations = [];
if (arr.length === 1) {
return [ arr ];
}
for (var i = 0; i < arr.length; i++) {
var subPerms = permute_Taylor_Hakes(arr.slice(0, i).concat(arr.slice(i + 1)));
for (var j = 0; j < subPerms.length; j++) {
subPerms[j].unshift(arr[i]);
permutations.push(subPerms[j]);
}
}
return permutations;
}
var Combinatorics = (function () {
'use strict';
var version = "0.5.2";
/* combinatory arithmetics */
var P = function(m, n) {
var p = 1;
while (n--) p *= m--;
return p;
};
var C = function(m, n) {
if (n > m) {
return 0;
}
return P(m, n) / P(n, n);
};
var factorial = function(n) {
return P(n, n);
};
var factoradic = function(n, d) {
var f = 1;
if (!d) {
for (d = 1; f < n; f *= ++d);
if (f > n) f /= d--;
} else {
f = factorial(d);
}
var result = [0];
for (; d; f /= d--) {
result[d] = Math.floor(n / f);
n %= f;
}
return result;
};
/* common methods */
var addProperties = function(dst, src) {
Object.keys(src).forEach(function(p) {
Object.defineProperty(dst, p, {
value: src[p],
configurable: p == 'next'
});
});
};
var hideProperty = function(o, p) {
Object.defineProperty(o, p, {
writable: true
});
};
var toArray = function(f) {
var e, result = [];
this.init();
while (e = this.next()) result.push(f ? f(e) : e);
this.init();
return result;
};
var common = {
toArray: toArray,
map: toArray,
forEach: function(f) {
var e;
this.init();
while (e = this.next()) f(e);
this.init();
},
filter: function(f) {
var e, result = [];
this.init();
while (e = this.next()) if (f(e)) result.push(e);
this.init();
return result;
},
lazyMap: function(f) {
this._lazyMap = f;
return this;
},
lazyFilter: function(f) {
Object.defineProperty(this, 'next', {
writable: true
});
if (typeof f !== 'function') {
this.next = this._next;
} else {
if (typeof (this._next) !== 'function') {
this._next = this.next;
}
var _next = this._next.bind(this);
this.next = (function() {
var e;
while (e = _next()) {
if (f(e))
return e;
}
return e;
}).bind(this);
}
Object.defineProperty(this, 'next', {
writable: false
});
return this;
}
};
/* power set */
var power = function(ary, fun) {
var size = 1 << ary.length,
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'index');
addProperties(that, {
valueOf: sizeOf,
init: function() {
that.index = 0;
},
nth: function(n) {
if (n >= size) return;
var i = 0,
result = [];
for (; n; n >>>= 1, i++) if (n & 1) result.push(this[i]);
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
},
next: function() {
return this.nth(this.index++);
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};
/* combination */
var nextIndex = function(n) {
var smallest = n & -n,
ripple = n + smallest,
new_smallest = ripple & -ripple,
ones = ((new_smallest / smallest) >> 1) - 1;
return ripple | ones;
};
var combination = function(ary, nelem, fun) {
if (!nelem) nelem = ary.length;
if (nelem < 1) throw new RangeError;
if (nelem > ary.length) throw new RangeError;
var first = (1 << nelem) - 1,
size = C(ary.length, nelem),
maxIndex = 1 << ary.length,
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'index');
addProperties(that, {
valueOf: sizeOf,
init: function() {
this.index = first;
},
next: function() {
if (this.index >= maxIndex) return;
var i = 0,
n = this.index,
result = [];
for (; n; n >>>= 1, i++) {
if (n & 1) result[result.length] = this[i];
}
this.index = nextIndex(this.index);
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};
/* permutation */
var _permutation = function(ary) {
var that = ary.slice(),
size = factorial(that.length);
that.index = 0;
that.next = function() {
if (this.index >= size) return;
var copy = this.slice(),
digits = factoradic(this.index, this.length),
result = [],
i = this.length - 1;
for (; i >= 0; --i) result.push(copy.splice(digits[i], 1)[0]);
this.index++;
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
};
return that;
};
// which is really a permutation of combination
var permutation = function(ary, nelem, fun) {
if (!nelem) nelem = ary.length;
if (nelem < 1) throw new RangeError;
if (nelem > ary.length) throw new RangeError;
var size = P(ary.length, nelem),
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'cmb');
hideProperty(that, 'per');
addProperties(that, {
valueOf: function() {
return size;
},
init: function() {
this.cmb = combination(ary, nelem);
this.per = _permutation(this.cmb.next());
},
next: function() {
var result = this.per.next();
if (!result) {
var cmb = this.cmb.next();
if (!cmb) return;
this.per = _permutation(cmb);
return this.next();
}
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};
/* export */
var Combinatorics = Object.create(null);
addProperties(Combinatorics, {
C: C,
P: P,
factorial: factorial,
factoradic: factoradic,
permutation: permutation,
});
return Combinatorics;
})();
function permute_Technicalbloke(inputArray) {
if (inputArray.length === 1) return inputArray;
return inputArray.reduce( function(accumulator,_,index){
permute_Technicalbloke([...inputArray.slice(0,index),...inputArray.slice(index+1)])
.map(value=>accumulator.push([inputArray[index],value]));
return accumulator;
},[]);
}
var suite = new Benchmark.Suite;
var input = [0, 1, 2, 3, 4];
suite.add('permute_SiGanteng', function() {
permute_SiGanteng(input);
})
.add('permute_delimited', function() {
permute_delimited(input);
})
.add('permute_monkey', function() {
permute_monkey(input);
})
.add('permute_Oriol', function() {
permute_Oriol(input);
})
.add('permute_MarkusT', function() {
permute_MarkusT(input);
})
.add('permute_le_m', function() {
permute_le_m(input);
})
.add('permute_Urielzen', function() {
permute_Urielzen(input);
})
.add('permute_Taylor_Hakes', function() {
permute_Taylor_Hakes(input);
})
.add('permute_Combinatorics', function() {
Combinatorics.permutation(input).toArray();
})
.add('permute_Technicalbloke', function() {
permute_Technicalbloke(input);
})
.on('cycle', function(event) {
console.log(String(event.target));
})
.on('complete', function() {
console.log('Fastest is ' + this.filter('fastest').map('name'));
})
.run({async: true});<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/platform/1.3.4/platform.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.min.js"></script>Run-time results for Chrome 48:
var inputArray = [1, 2, 3];
var result = inputArray.reduce(function permute(res, item, key, arr) {
return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) { return [item].concat(perm); }) || item);
}, []);
alert(JSON.stringify(result));
I have improved SiGanteng's answer.
Now it is possible to call permute more than once, because permArr and usedChars are cleared each time.
function permute(input) {
var permArr = [],
usedChars = [];
return (function main() {
for (var i = 0; i < input.length; i++) {
var ch = input.splice(i, 1)[0];
usedChars.push(ch);
if (input.length == 0) {
permArr.push(usedChars.slice());
}
main();
input.splice(i, 0, ch);
usedChars.pop();
}
return permArr;
})();
}
function permute(input) {
var permArr = [],
usedChars = [];
return (function main() {
for (var i = 0; i < input.length; i++) {
var ch = input.splice(i, 1)[0];
usedChars.push(ch);
if (input.length == 0) {
permArr.push(usedChars.slice());
}
main();
input.splice(i, 0, ch);
usedChars.pop();
}
return permArr;
})();
}
document.write(JSON.stringify(permute([5, 3, 7, 1])));Some version inspired from Haskell:
perms [] = [[]]
perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ]
function perms(xs) {
if (!xs.length) return [[]];
return xs.flatMap(x => {
// get permutations of xs without x, then prepend x to each
return perms(xs.filter(v => v!==x)).map(vs => [x, ...vs]);
});
// or this duplicate-safe way, suggested by @M.Charbonnier in the comments
// return xs.flatMap((x, i) => {
// return perms(xs.filter((v, j) => i!==j)).map(vs => [x, ...vs]);
// });
// or @user3658510's variant
// return xs.flatMap((x, i) => {
// return perms([...xs.slice(0,i),...xs.slice(i+1)]).map(vs => [x,...vs]);
// });
}
document.write(JSON.stringify(perms([1,2,3])));Most answers to this question use expensive operations like continuous insertions and deletions of items in an array, or copying arrays reiteratively.
Instead, this is the typical backtracking solution:
function permute(arr) {
var results = [],
l = arr.length,
used = Array(l), // Array of bools. Keeps track of used items
data = Array(l); // Stores items of the current permutation
(function backtracking(pos) {
if(pos == l) return results.push(data.slice());
for(var i=0; i<l; ++i) if(!used[i]) { // Iterate unused items
used[i] = true; // Mark item as used
data[pos] = arr[i]; // Assign item at the current position
backtracking(pos+1); // Recursive call
used[i] = false; // Mark item as not used
}
})(0);
return results;
}
permute([1,2,3,4]); // [ [1,2,3,4], [1,2,4,3], /* ... , */ [4,3,2,1] ]
Since the results array will be huge, it might be a good idea to iterate the results one by one instead of allocating all the data simultaneously. In ES6, this can be done with generators:
function permute(arr) {
var l = arr.length,
used = Array(l),
data = Array(l);
return function* backtracking(pos) {
if(pos == l) yield data.slice();
else for(var i=0; i<l; ++i) if(!used[i]) {
used[i] = true;
data[pos] = arr[i];
yield* backtracking(pos+1);
used[i] = false;
}
}(0);
}
var p = permute([1,2,3,4]);
p.next(); // {value: [1,2,3,4], done: false}
p.next(); // {value: [1,2,4,3], done: false}
// ...
p.next(); // {value: [4,3,2,1], done: false}
p.next(); // {value: undefined, done: true}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With