Получить каждую возможную комбинацию 0 и 1 в двумерном массиве (nxn) - PullRequest
Новая
       4

Получить каждую возможную комбинацию 0 и 1 в двумерном массиве (nxn)

1 голос
/ 06 апреля 2020

Я пытаюсь сгенерировать метод, возвращающий массив из каждых 2d массивов, состоящих из 0 и 1 в JS в 2d квадрате массива. По сути, это тот же вопрос, что и этот: Создайте все возможные комбинации в двумерном массиве

Но в Javascript, без пакетов, и добавьте параметр для размера массива. Например, 2x2 будет: 

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

Я пробовал с рекурсией, но безуспешно, любая помощь будет признательна.

Редактировать:

Я пытаюсь = g, чтобы написать рекурсивную функцию для решения этой проблемы.

На данный момент у меня есть этот метод: 

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

, который производит этот вывод: 

[
  [ [ 1, 1 ], [ 1, 1 ] ],
  [ [ 1, 1 ], [ 1, 1 ] ],
  [ [ 1, 1 ], [ 1, 1 ] ],
  [ [ 1, 1 ], [ 1, 1 ] ],
]

1 Ответ

1 голос
/ 06 апреля 2020

Интересно, что различные комбинации для аргумента n могут быть представлены как все двоичные последовательности для чисел 0 до числа 2 n 2 -1 .

Поскольку мы имеем дело с потенциально большими числами, нижеприведенная реализация использует новый тип данных BigInt для представления этих чисел , Он берет каждое из этих чисел, дополняет двоичную строку до фиксированной длины, а затем разбивает строку на двумерный массив.

Производительность, вероятно, не впечатляет, но я подумал, что это интересный подход. 

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

Примечание: BigInt является функцией ECMAScript 2020, поэтому ваш пробег может отличаться.

...