1

I am trying to generate a method returning an array of every 2d arrays composed of 0's and 1's in JS in a 2d squared array. Basically, this is the same question as this one : Make every possible combination in 2D array

But in Javascript, without packages, and add a parameter for the size of the array. Like, a 2x2 would be :

let arr = new Array(2).fill(0).map(() => new Array(2).fill(0))
combinations(arr, 2) { ... }

returns : 
[
    [ 
        [0, 0],
        [0, 0]
    ],
    [
        [0, 0],
        [0, 1]
    ],
    [...],
    [
        [1, 1],
        [1, 1]
    ]
]

I've tried with recursion but without success, any help would be appreciated.

Edit :

I am tryin =g to write a recursive function to solve this problem.

For now, I have this method : 

let arr = new Array(2).fill(0).map(() => new Array(2).fill(0))
const generateCombination = (arr, n) => {
    let ret = [];
    let tmp;
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        ret.push(arr)
        arr[i][j] = 1;
        generateCombination(arr.slice(), n-1)
      }
    }
    return ret;
  };

which produces this output :

[
  [ [ 1, 1 ], [ 1, 1 ] ],
  [ [ 1, 1 ], [ 1, 1 ] ],
  [ [ 1, 1 ], [ 1, 1 ] ],
  [ [ 1, 1 ], [ 1, 1 ] ],
]
Sam-Sam
  • 21
  • 3
  • 2
    Please go read [ask]. You should always _show us_, what you tried ([mre]), even if those attempts were not completely successful. – CBroe Apr 06 '20 at 08:11

1 Answers1

1

Interestingly, the different combinations for an argument n can be represented as all the binary sequences for the numbers 0 to the number 2n2-1.

Because we're dealing with potentially large numbers, the implementation below uses the new BigInt data type to represent those numbers. It takes each of those numbers, pads the binary string to a fixed length, and then chunks the string to a two-dimensional array.

Performance is probably not amazing, but I thought it was an interesting approach.

const combinations = (n) => {
  const bits = n ** 2;
  const max = 2n ** BigInt(bits);
  const result = [];
  
  for (let i = 0n; i  < max; i++) {
    const s = i.toString(2).padStart(bits, '0');
    
    result.push([...s].map(Number).reduce((a, _, i, array) => (i % n)
        ? a
        : [...a, array.slice(i, i + n)], []));
  }
  return result;
}

console.log(combinations(2));

Note: BigInt is an ECMAScript 2020 feature, so your mileage may vary.

Robby Cornelissen
  • 91,784
  • 22
  • 134
  • 156
  • 1
    I see. This is indeed an interesting approach, you've taken the problem from a different angle than me. I will try this, and maybe try to adapt it to make it a bit simpler to understand. Thank you! – Sam-Sam Apr 06 '20 at 09:06
  • 1
    The most complex looking part is the part that chunks the array, adapted from a question [here](https://stackoverflow.com/questions/8495687/split-array-into-chunks). – Robby Cornelissen Apr 06 '20 at 09:17
  • I've tried your solution, but it crashes on node for n = 5. I guess I need to look for a recursive solution of this problem without going through BigInts as you did. Ideally, I would like it to run up until n = 7 or 8 – Sam-Sam Apr 06 '20 at 09:26
  • 1
    Well, for n=5, you're looking at 33554432 2-dimensional arrays, so your process might just be running out of memory. It might be better to write a generator function. – Robby Cornelissen Apr 06 '20 at 09:32
  • Now, I'm looking at a way to do the exact same thing recursively with 2 loops, how would you achieve that ? Edit: I have updated the question, and the sample I provided – Sam-Sam Apr 07 '20 at 10:35