Permutation algorithm with JavaScript

Next I write a program to display the permutations for n numbers with JavaScript. First, we need to understand that from these n numbers, we can first take any one number from it, and the (n-1) numbers remaining has the similar property as the n numbers, we need to find the permutations for the (n-1) numbers, and from these (n-1) numbers, we take any one of them and there are (n-2) numbers which we need to find the permutations of them. So the whole process will stop when there is only one number left, we will can display the permutations. It is a recursive process. The code can be shown below:

 

<script type="text/javascript">
    var count=0;
    function permute(pre,cur){	
        var len=cur.length;
        for(var i=0;i<len;i++){
            var p=clone(pre);
            var c=clone(cur);
            p.push(cur[i]);
            remove(c,cur[i]);
            if(len>1){
                permute(p,c);
            }else{
                print(p);
                count++;
            }
        }
    }
    function print(arr){
        var len=arr.length;
        for(var i=0;i<len;i++){
            document.write(arr[i]+" ");
        }
        document.write("<br />");
    }
    function remove(arr,item){
        if(contains(arr,item)){
            var len=arr.length;
            for(var i = len-1; i >= 0; i--){ // STEP 1
                if(arr[i] == item){             // STEP 2
                    arr.splice(i,1);              // STEP 3
                }
            }
        }
    }
    function contains(arr,value){
        for(var i=0;i<arr.length;i++){
            if(arr[i]==value){
                return true;
            }
        }
        return false;
    }
    function clone(arr){
        var a=new Array();
        var len=arr.length;
        for(var i=0;i<len;i++){
            a.push(arr[i]);
        }
        return a;
    }
</script> 

There are some supplemental functions which is to simplify the functions such as contains(0, remove(), clone(). 

contains() checks whether an element is in an array, if in, returns true, otherwise return false;

remove() is to remove an element from an array;

clone(0 is to clone an array to create the exact copy of the original array.

 

The code has the function permutation, it takes two parameters, the pre and cur. pre is an array which store the numbers which have been taken from the n numbers and the cur array store the remaining elements in these n numbers. Every time when an element is taken from the n numbers, it will be pushed to the pre array and it will be removed from the cur array and this process wll continue until only one number left in cur array. Then the display process will start.

 

Test result for 4 numbers 1,2,3,4, the result permutations are:

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
Total permutations : 24

 

Hope it can help you. Enjoy!