Program to solve Circular Combinatorics Program Problem

user_7402323 0
Viewed 129

I understand how to do this by problem by hand, but I want to create a Javascript program to complete this for (c,r), with c being containers and r being rocks.

Setting You have 4 indistinguishable rocks of all the same type. You also have 10 containers. Each container can hold 0 rocks or 1 rock. All 4 rocks need to be used in every arrangement leaving 6 0s in each arrangement.

I believe there should be somewhere in the neighborhood of 210 possibilities (10!)/ (4! * (10-4)!) based on a combinations generator.

for example, these are examples of the possibilities:

1111000000
1110100000
1110001000
0000001111
0101010100

What I am looking for is a javascript function that will spit out the 210 arrays such that it is [1,1,1,1,0,0,0,0,0,0] with an input of a number of rocks and containers.

node.js combinatorics math algorithm javascript
4 Answers

I tried @JonTrent's way to do it (counting from 0 to 2^c - 1), this is a really clever way to do it:

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

user_19137290

I simply copied the answer from here, Permutations in JavaScript?

And then add as many space as you want into the input array. Try any solution you want from that post then.

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

user_2880960

You could seach for the next element to swap and reorder the right left over value to the most right side.

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>

user_14476750 
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);
user_93188990
Related