Python генерирует все возможные комбинации матрицы - PullRequest
Новая
       30

Python генерирует все возможные комбинации матрицы

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

Мне нужно сгенерировать все комбинации матрицы в Python.Входными данными будут два целых числа n и m, и мне нужно сгенерировать все возможные состояния этой матрицы с 1 и 0 в качестве возможных значений.

Например: 

n = 3 m = 2
[[0 0 0] [1 0 0] [1 1 0]
 [0 0 0] [0 0 0] [0 0 0]
 [0 0 0],[0 0 0],[0 0 0] . . . . .
]

Есть личистый и эффективный способ сделать это, учитывая, я не буду знать значения для п и м до времени выполнения?Максимальное используемое значение будет n = 16 м = 16.

Ответы [ 2 ]

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

Одним из способов является генерирование всех двоичных последовательностей длиной m*n в понимании списка и преобразование их в вложенный список в форме (m,n) на каждой итерации.

Простой способ создать все последовательности - взять декартово произведение 01 с n*m повторениями, что даст 2^(m*n) комбинаций: 

from itertools import product
m=3
n=3

x = [[list(i[x:x+m]) for x in range(0, len(i), m)] for i in product("01", repeat=m*n)]

Выход 

[[['0' '0' '0']
  ['0' '0' '0']
  ['0' '0' '0']]

 [['0' '0' '0']
  ['0' '0' '0']
  ['0' '0' '1']]

 [['0' '0' '0']
  ['0' '0' '0']
  ['0' '1' '0']]
 ...

print(len(x))
# 512
0 голосов
/ 28 февраля 2019

Если вы хотите получить все матрицы одновременно, просто создайте плоские списки, используя itertools.product и numpy.reshape их: 

from itertools import product
import numpy as np

n, m = 2, 2

x = product([1, 0], repeat=n*m)
x = np.reshape(list(x), (-1, n, m))
print(x)

С выводом для2x2: 

array([[[1, 1],
        [1, 1]],

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

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

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

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

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

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

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

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

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

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

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

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

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

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

       [[0, 0],
        [0, 0]]])

Обратите внимание, что для n, m = 16, 16 существует 2**(16*16) комбинаций, что составляет 10**77, слишком много, чтобы поместиться в память.В этом случае вам, вероятно, придется обрабатывать каждую матрицу самостоятельно: 

def get_combinations(n, m):
    for flat in product([1, 0], repeat=n*m):
        yield np.reshape(flat, (n, m))

, которую вы можете использовать следующим образом: 

from itertools import islice

for m in islice(get_combinations(3, 3), 3):  # only get the first three
    print(m)

[[1 1 1]
 [1 1 1]
 [1 1 1]]
[[1 1 1]
 [1 1 1]
 [1 1 0]]
[[1 1 1]
 [1 1 1]
 [1 0 1]]
...