F #: двумерный массив - генерировать все возможные двоичные комбинации - PullRequest
Новая
       23

F #: двумерный массив - генерировать все возможные двоичные комбинации

0 голосов
/ 26 февраля 2019

Какой подход вы бы использовали для генерации набора NxN-матриц, содержащих только нули и единицы, представляющие все возможные различные комбинации? 

let matrix Array2D.init N N (fun x y -> something)

Если вы не знаете F #, тогда псевдокод будет также вкладом,

Итак, мне нужен список / массив всех различных комбинаций матриц

Ответы [ 2 ]

0 голосов
/ 27 февраля 2019

Итак, я думаю, что самая сложная часть - это создание списка элементов.Мы можем сделать это рекурсивно.

Базовый случай прост.Для матрицы 1x1 у вас есть 1 элемент, который может иметь только две комбинации: [|[|0|]; [|1|]|].

Для элементов 2x2 у нас есть 2 ^ 2 = 4 элемента.Каждый из них может быть либо 1, либо 0, поэтому возможны 2 ^ 4 = 16 комбинаций.Чтобы получить все возможные комбинации для этого массива 2x2, мы можем думать о нем как о массиве длины 4.

Но сначала давайте подумаем о массиве длины 2. Затем мы должны найти все комбинации между[|[|0|]; [|1|]|] и [|[|0|]; [|1|]|].Это было бы [|[|0; 0|]; [|0;1|]; [|1;0|]; [|1; 1|]|].К счастью, есть функция с именем Array.allPairs, которая сгенерирует массив всех возможных комбинаций между двумя массивами, который уже делает это для нас!

Итак, мы можем применить Array.allPairs к каждому элементу нашего массивадлина 4 последовательно, чтобы получить все возможные комбинации для всей матрицы, используя Array.reduce.Я создаю функцию с именем pairsToArray, которая в основном выравнивает структуру данных. 

let pairsToArray x = Array.concat [|fst x; snd x|]

let rec binary N = 
    match N with
    | 0 -> [||]
    | 1 -> [|[|0|]; [|1|]|]
    | n -> let elements = n*n
           let combinations = Array.init elements (fun i -> binary 1)
           let result = Array.reduce (fun acc i -> Array.allPairs acc i |> Array.map pairsToArray) combinations
           result

Теперь все, что остается, - это преобразовать это в Array2D.Нечто подобное должно сделать трюк 

let c = binary 2
c |> Array.map (fun i -> Array2D.init 2 2 (fun j k -> i.[j+k*2]))

для случая 2x2

0 голосов
/ 27 февраля 2019

Может быть, что-то вроде этого 

let rec addOne (N1: int, N2: int) (M: int[,]) (i: int, j: int)=
  if M.[i,j] = 0
   then M.[i,j] <- 1
        true
   else M.[i,j] <- 0
        let newi, newj =
            if i < N1-1
             then (i+1,j)
             else (0,j+1)
        if newj = N2
         then false
         else addOne (N1, N2) M (newi,newj)

в сочетании с этим 

let N = 3
let M: int[,] = Array2D.zeroCreate N N
let mylist =
  [ yield M;
    while addOne (N,N) M (0,0)
       do yield Array2D.copy M ]

Я не знаю, имеет ли это смысл.Это метод, чтобы найти «следующую» матрицу, а затем составить список всех матриц, с которыми мы сталкиваемся таким образом.

edit: заменил bool на int (0 и 1), чтобы лучше соответствовать исходному вопросу.

...