排列組合算法的javascript實現 - kaiye－IT工程師數位筆記本

文章出處

命題：從成員數為N的集合S中，選出M個元素，分別求其排列與組合結果集，即 A(N, M)與C(N, M)

js解法：

 1 function queue(arr, size){
 2   if(size > arr.length){ return;}
 3   var allResult = [];
 4 
 5   (function(arr, size, result){
 6     if(result.length == size){
 7       allResult.push(result);
 8     }else{
 9       for(var i =0 ,len = arr.length;i < len; i++){
10         var newArr = [].concat(arr),
11             curItem = newArr.splice(i,1);
12         arguments.callee(newArr, size, [].concat(result,curItem));
13       }
14     }
15   })(arr, size, []);
16 
17   return allResult;
18 }
19 
20 
21 function choose(arr, size ){
22   var allResult = [];
23 
24   (function(arr, size, result){
25     var arrLen = arr.length;
26     if(size > arrLen){
27       return;
28     }
29     if(size == arrLen){
30       allResult.push([].concat(result, arr))
31     }else{
32       for(var i =0 ; i < arrLen; i++){
33         var newResult = [].concat(result);
34         newResult.push(arr[i]);
35 
36         if(size == 1){
37           allResult.push(newResult);
38         }else{
39           var newArr = [].concat(arr);
40           newArr.splice(0, i +　1);
41           arguments.callee(newArr, size - 1, newResult);
42         }
43       }
44     }
45   })(arr, size, []);
46 
47   return allResult;
48 }
49 
50 function showResult(result){
51   console.log('The number of result sets: ' + result.length );
52   for(var i=0 , len = result.length;i < len; i++){
53     console.log(result[i]);
54   }
55 }
56 
57 
58 var arr = ['姬光','王子', '三桂','科長'];
59 
60 showResult(choose(arr, 4));
61 showResult(queue(arr, 4));