7

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.

FDRH
  • 209
  • 3
  • 11
  • 1
    Basically you're looking for all binary numbers from 0 - 1023 ( 2 ^ 10 digits - 1 ) that have 4 bits set. Quick and dirty way will be to loop from 0 to 1023, convert this number to binary ( ie, `toString(2)` ) and count the number of 1's. If there are four 1's, keep the result, otherwise move on to the next number. – Trentium Jun 28 '20 at 15:28
  • @JonTrent I posted an answer based on your idea which I find fantastic. if you want to post this as an answer yourself, please do! It's your idea – blex Jun 28 '20 at 15:47
  • 1
    @blex, it's all you! You did the heavy lifting. Plus your approach to splitting on the 1's to count the 1's is a neat approach. – Trentium Jun 28 '20 at 17:34

4 Answers4

3

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!`);
blex
  • 24,941
  • 5
  • 39
  • 72
0

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']))
windmaomao
  • 7,120
  • 2
  • 32
  • 36
  • This does not solve the problem, however. If we imagine there are 3 containers and 2 rocks, (`permutator(['1', '1', '0'])`), we get duplicate combinations – blex Jun 28 '20 at 15:35
  • 1
    oh, then search `permutation` with unique result then. Try https://stackoverflow.com/questions/40264376/get-all-the-possible-unique-permutations – windmaomao Jun 28 '20 at 15:47
0

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>
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
0
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
  • 209
  • 1
  • 5