解决循环组合程序问题的程序

Question

我知道如何手工解决这个问题，但我想创建一个 Javascript 程序来为 (c,r) 完成这个，其中 c 是容器，r 是岩石。

设置你有 4 块相同类型的无法区分的岩石。您还有 10 个容器。每个容器可以容纳 0 个岩石或 1 个岩石。每个排列都需要使用所有 4 个岩石，每个排列中留下 6 个 0。

我认为基于组合生成器，应该有 210 种可能性 (10!)/ (4! * (10-4)!) 附近的某处。

例如，这些是可能性的例子：

我正在寻找的是一个 javascript 函数，它将吐出 210 个数组，使得它 [1,1,1,1,0,0,0,0,0,0] 具有一些岩石和容器的输入。

Answer 1

我只是从这里复制了答案，Permutations in JavaScript?

然后在输入数组中添加任意数量的 space。然后从 post 中尝试任何你想要的解决方案。

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']))

Answer 2

我尝试了@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!`);

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>

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);

解决循环组合程序问题的程序

Program to solve Circular Combinatorics Program Problem

javascript

node.js

algorithm

math

combinatorics