Problem
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
JavaScript Code
function permute(num) { var result = []; //start from an empty list result.push([]); for (var i = 0; i < num.length; i++) { //list of list in current iteration of the array num var current = []; for (var k=0;k<result.length;k++) { var l = result[k]; // # of locations to insert is largest index + 1 for (var j = 0; j < l.length+1; j++) { // + add num[i] to different locations l.splice(j, 0, num[i]); var temp = JSON.parse(JSON.stringify(l)); if(indexOf(current, temp, arraysIdentical) == -1) { current.push(temp); } // - remove num[i] add l.splice(j,1); } } result = JSON.parse(JSON.stringify(current)); } return result; } function arraysIdentical(arr1, arr2) { var i = arr1.length; if (i !== arr2.length) { return false; } while (i--) { if (arr1[i] !== arr2[i]) { return false; } } return true; } function indexOf(arr, val, comparer) { for (var i = 0, len = arr.length; i < len; ++i) { if ( i in arr && comparer(arr[i], val) ) { return i; } } return -1; }
0 comments:
Post a Comment