c++ - 带扭曲的二项式系数

现在，枚举集合中的所有 k=4 组合

Set = [1; 2; 3; 4; 5; 6; 7; 8]

我使用预先构建的 Matlab 函数 nchoosek 来计算二项式系数。一次取 k 的 n 个事物的组合数由 n!/((n-k)!k!) 计算。

现在，假设我有一组包含 n = 8 个元素的数据:

Set = [1.A; 2.B; 3.C; 4.D; 5.B; 6.D; 7.C; 8.A]

我想枚举“Set”中 4 个整数的所有组合，但有一点需要注意:我必须在任何组合中只有一个具有相同字母的元素(顺序无关紧要)。例如:

[1.A; 2.B; 6.D； 7.C] 将是一个有效的组合，但不是 [1.A; 2.B; 6.D； 8.A]。

有 [1.A; 2.B; 6.D； 7.C]，我仍然必须生成组合[8.A; 2.B; 6.D； 7.C]

不必生成 70 个组合，因为 A、B、C 和 D 出现了 2 次，我只需要生成 2*2*2*2 = 16 个组合。 70-16 = 54 种其他组合与我的问题无关，我宁愿不生成它们，因为它的计算量越来越大。目前，我生成了 70 个组合，然后使用一些逻辑来删除所有不相关的组合。

所以，我的问题是:

这种类型的组合有名字吗？ (可以帮助我搜索信息并更好地理解问题)

是否有一些现有的算法允许计算？在 Matlab 或 C++ 中。请，如果它充满了正则表达式，欢迎提供一些解释......

最佳答案

一般递归(如果堆叠则迭代)算法:

combs(index,multiset,k,result):
  if length of result == k:
    output result
    return
  if length of result + length of multiset - index < k:
    return
  for j in multiset[index]:
    combs(index + 1,multiset,k,result with multiset[index][j] added)
  combs(index + 1,multiset,k,result)

JavaScript 示例:

function combs(i,multiset,k,result){
  if (result.length == k){
    console.log(result);
    return;
  }
  if (result.length + multiset.length - i < k)
    return;
  for (var j=0; j<multiset[i].length; j++){
    _result = result.slice();
    _result.push(multiset[i][j]);
    combs(i + 1,multiset,k,_result);
  }
  combs(i + 1,multiset,k,result);
}

combs(0,[["1.A","8.A"],["2.B","5.B"],["3.C","7.C"],["4.D","6.D"]],4,[]);

关于c++ - 带扭曲的二项式系数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32080072/