解决循环组合问题的程序

Question

我知道如何手动解决这个问题，但我想创建一个Javascript程序来为 (c,r) 进行计算，其中 c 代表容器，r 代表石头。

场景 你有4个无法区分的相同类型的石头。你也有10个容器。每个容器可以容纳0个或1个石头。所有4个石头需要在每种排列中都被使用，使得每种排列中都有6个0。

我认为根据组合生成器，可能会有大约210种可能性（10！）/ （4！*（10-4）！）。

例如，以下是可能性的一些示例：

1111000000
1110100000
1110001000
0000001111
0101010100

我需要的是一个 JavaScript 函数，可以根据岩石和容器数量输出 210 个这样的数组: [1,1,1,1,0,0,0,0,0,0]。

- FDRH

---

基本上，您要查找从0到1023（2 ^ 10位-1）的所有二进制数字，其中有4个位设置。快速且简单的方法是从0循环到1023，将此数字转换为二进制（即toString（2）），并计算1的数量。如果有四个1，则保留结果，否则继续下一个数字。 - Trentium

@JonTrent 我基于你的想法发布了一篇答案，我觉得它很棒。如果你想自己将其发布为答案，请随意！毕竟这是你的想法。 - blex

@blex，全靠你了！你做了很多工作。此外，你在1的位置分割并计算1的数量的方法非常巧妙。 - Trentium

Answer 1

我尝试了@JonTrent的方法（从0到2^c - 1计数），这是一个非常聪明的方法：

function getCombinations(c, r) {
  const max = Math.pow(2, c);
  const res = [];
  for (let i = 0; i < max; i++) {
    const binary = i.toString(2);
    if (binary.split("1").length - 1 === r) {
      res.push(
        binary.padStart(c, '0')
              .split('')
              .map(n => parseInt(n, 10))
      );
    }
  }
  return res;
}

const res = getCombinations(10, 4);
// [
//  [0,0,0,0,0,0,1,1,1,1],
//  [0,0,0,0,0,1,0,1,1,1],
//  [0,0,0,0,0,1,1,0,1,1]
//  ...
// ]

document.body.innerHTML = `<pre>${res.map(x => x.join('')).join('\n')}</pre>`;
console.log(`${res.length} combinations found!`);

- blex

Answer 2

我只是从这里复制了答案，JavaScript中的排列组合？

然后在输入数组中添加任意数量的空格。从那篇帖子中尝试任何你想要的解决方案。

function permutator(inputArr) {
  var results = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];

    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }

    return results;
  }

  return permute(inputArr);
}

console.log(permutator(['a', ' ', 'b', 'c']))

- windmaomao

---

然而，这并没有解决问题。如果我们想象有3个容器和2块石头，(permutator(['1', '1', '0']))，我们会得到重复的组合。 - blex

哦，那么就搜索具有唯一结果的“排列”吧。请尝试访问 https://stackoverflow.com/questions/40264376/get-all-the-possible-unique-permutations - windmaomao

Answer 3

你可以搜索下一个要交换的元素，并将右侧剩余值重新排序到最右侧。

function perm(string) {
    var array = [...string],
        l = array.length - 1,
        r = array.length - 1;
    
    // either starts with zero from end or with one and get only ones
    while (array[l] === '0') l--;
    while (array[l] === '1') l--;
    if (l < 0) return;
    [array[l], array[l + 1]] = [array[l + 1], array[l]];
    while (r > ++l) {
        if (array[l] === '1') {
            [array[l], array[r]] = [array[r], array[l]];
            r--;
        }
    }
    return array.join('');
}

var string = '0000001111',
    i = 0,
    log = document.getElementById('out');
    
do out.innerHTML += `${(++i).toString().padStart(3, ' ')} ${string}\n`;
while (string = perm(string));

<pre id="out"></pre>

- Nina Scholz

Answer 4

function circular(c, r) {
    let arrs = [[]];
    for (let i = 0; i < c; i++) {
        let len = arrs.length;
        for (let j = 0; j < len; j++) {
            arr = arrs.shift();
            if (arr.filter((el) => el === 0).length < c - r) {
                arrs.push(arr.concat([0]));
            }
            if (arr.filter((el) => el === 1).length < r) {
                arrs.push(arr.concat([1]));
            }
        }
    }
    return arrs;
}

console.log(circular(3, 1));
console.log(circular(10, 4).length);

- willystyle