算法讨论:从任意长度(N)的数组中取任意个(M)不重复的元素的所有组合
发布于 1 年前 作者 coordcn 1998 次浏览 来自 问答

就是排列组合中的组合问题,比如用在双色球选号码上。

体育彩票那个是排列问题,大家有兴趣的也可以贡献代码。

var data = [0, 1, 2, 3, 4];
var out = [
	[0, 1, 2],
	[0, 1, 3],
	[0, 1, 4],
	[0, 2, 3],
	[0, 2, 4],
	[0, 3, 4],
	[1, 2, 3],
	[1, 2, 4],
	[1, 3, 4],
	[2, 3, 4]
];
6 回复
function gencombine(n, m) {
  var combine = [];
  if (m > n) return combine;

  var stack = [];
  var first = []
  for (var i = 0; i < m; i++) {
    stack[i] = i;
    first[i] = i;
  }
  combine.push(first);

  var last = [];
  var end = n - m;
  for (var i = 0; i < m; i++) {
    last[i] = end + i;
  }

  var pos = m - 1;
  var lastm = m - 1;
  var temp;
  while (true) {
    if (stack[pos] < last[pos]) {
      stack[pos]++;
      temp = stack[pos];
      pos++;
      if (pos <= lastm) {
        stack[pos] = temp;
      }
    } else {
      pos--;
      if (pos < 0) break;
    }

    if (pos > lastm) {
      var tmp = [];
      for (var i = 0; i < m; i++) {
        tmp[i] = stack[i];
      }
      combine.push(tmp);
      pos = lastm;
    }
  }

  return combine;
}

《算法导论 从入门到放弃》

@coordcn 赞一个,这种帖子有意思

var out = []; var data = [0, 1, 2, 3, 4]; var res = [];

function combi(arr, n, res){ if(n == 0){ out.push(res); return ; } if(arr.length == n){ out.push(res.concat(arr)); return ; }

for(var i=0;i<=arr.length-n;i++){ var temp = res.slice(0); temp.push(arr[i]); combi(arr.slice(i+1), n-1, temp); }

}

combi(data, 3, res); console.log(out);

递归思想,可以简化代码

@FujiBilly 的确,用第归简单得多了。

回到顶部