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:

Blogroll

Follow this blog by Email

Popular Posts