计算12栅格的排列组合 - CNode技术社区

const TOTAL=5;
const LIMIT=4;
for(a=0;a<=LIMIT;a++)
for(b=0;b<=LIMIT;b++)
for(c=0;c<=LIMIT;c++)
for(d=0;d<=LIMIT;d++)
for(e=0;e<=LIMIT;e++)
if (a+b+c+d+e == TOTAL)
 console.log([a,b,c,d,e]);

这是4栅格总宽度之和是5的全排列，这个程序能转成递归形式吗？

pfcoder 1楼•9 年前

转换成排列组合问题，一个粗糙的算法，包含三步：1. 计算出最大子元素数组seedsPool, 2.组合方式列出满足和， 3.补0全排列

function swap(arr, i, j) {
   if(i != j) {
       var temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
   }
}

function perm(arr) {
   var repeatCheck = {};
   (function fn(n) {
       for(var i = n; i < arr.length; i++) {
           swap(arr, i, n);
           if(n + 1 < arr.length - 1)
               fn(n + 1);
           else {
               if (!repeatCheck[arr.toString()]) {
                   console.log(arr); //显示一组结果
                   repeatCheck[arr.toString()] = true;
               }
           }

           swap(arr,i,n);
       }
   })(0);
}

function combine(arr, num, expectSum) {
   var repeatCheck = {};
   var r = [];
   (function f(t, a, n) {
       if (n == 0) {
           // perform repeat check first
           if (repeatCheck[t.toString()]) {
               return r;
           }
           var sum = 0;
           for (var i = 0; i < t.length; ++i) {
               sum += t[i];
           }
           if (sum == expectSum) {
               repeatCheck[t.toString()] = true;
               return r.push(t);
           } else {
               return r;
           }
       }
       for (var i = 0, l = a.length; i <= l - n; i++) {
           f(t.concat(a[i]), a.slice(i + 1), n - 1);
       }
   })([], arr, num);
   return r;
}

var m = 4, n = 5;
var expectSum = 5;

// Step1 build seeds pool
var seedsPool = [];
for (var i = 1; i <= m; ++i) {
   var cnt = Math.floor(expectSum / i);
   for (var j = 0; j < cnt; ++j) {
       seedsPool.push(i);
   }
}

// Step2 get min combine

for (var i = 1; i <= n; ++i) {
   var result = combine(seedsPool, i, expectSum);
   if (result.length > 0) {
       for (var k = 0; k < result.length; ++k) {
           var combineArray = result[k];
           if (combineArray.length < n) {
               // fill 0
               var miss = n - combineArray.length;
               for (var j = 0; j < miss; ++j) {
                   combineArray.push(0);
               }
           }
           perm(combineArray);
       }
   }
}