Эта проблема на самом деле является только проблемой грачей с доской n x n и ладьями m < n. Вот способ решения проблемы, который, хотя и не является оптимальным, но я надеюсь, вы найдете его интересным.
Сначала мы определим альтернативный способ описания двоичной матрицы размером n x n. Рассмотрим разбиение n чисел на пути и циклы. У строки есть единица, если она имеет входящее ребро. Источник входящего фронта указывает на столбец, в котором он находится. Примеры:
0->2, 1
Row 2 has a one in column zero since it has an incoming edge from 0
0 0 0
0 0 0
1 0 0
---
0->2->0, 1->1
Row 2 has a one in column 0 since it has an incoming edge from 0
Row 0 has a one in column 2 since it has an incoming edge from 2
Row 1 has a one in column 1 since it has an incoming edge from 1
0 0 1
0 1 0
1 0 0
---
- Таким образом, мы сначала разбьем
n числа на npart разбиения. (Нам нужно будет рассмотреть все разделы) - пример: мы разбиваем
0, 1, 2, 3 на 2 раздела: [0, 1, 2], [3].
- Мы разрешим каждому разделу любой вид цикл или путь (обратите внимание, что пути не являются циклическими c). (Нам нужно будет рассмотреть все комбинации циклов / путей)
- пример: мы позволяем
[0, 1, 2] формировать цикл и [3] формировать путь.
- Мы переставлять каждый раздел в зависимости от того, цикл это или путь. (мы выполним эту часть рекурсивно, чтобы рассмотреть все схемы)
- Пример:
[0, 1, 2] может образовывать только циклы 0-1-2-0 и 0-2-1-0. Обратите внимание, что 1-2-0-1 совпадает с 0-1-2-0. - Пример: если мы выбрали
[0, 1, 2] для формирования элементов пути, то все перестановки длины 3 действительны: т.е. 0-1-2, 0-2-1, 1-0-2, 1-2-0, 2-0-1, 2-1-0.
import numpy as np
import itertools
import more_itertools
def printMatrix(part, iscyc):
ones = -1*np.ones(n, dtype=int) # ones[2] = 4 means row 2 col 4 is 1, ones[2] = -1 means row 2 is all 0
for i, p in enumerate(part):
for j in range(len(p)-1):
ones[p[j+1]] = p[j]
if iscyc[i]:
ones[p[0]] = p[-1]
for r in range(n):
for c in range(n):
print(f"{1 if c == ones[r] else 0} ", end="")
print("")
print("")
def permute_part(head, tail, iscyc):
# head contains permuted partitions
# tail contains all partitions that haven't been permuted yet
global count
if not tail:
# empty tail means that all partitions have been permuted, and we have arrived at a valid solution
count += 1
printMatrix(head, iscyc)
return
p = tail[0]
perms = list(itertools.permutations(p))
while perms:
perm = perms.pop()
if iscyc[len(head)]:
# only keep distinct cycles in permutations
cshifts = list(more_itertools.circular_shifts(perm))
perms = [x for x in perms if x not in cshifts]
permute_part(head+[list(perm)], tail[1:], iscyc)
def all_part(part, iscyc):
permute_part([], part, iscyc)
n = 2
count = 0
for part in more_itertools.set_partitions(range(n)):
npart = len(part)
for iscyc in itertools.product(range(2), repeat=npart):
# i-th element in iscyc tells us whether partition i is a cycle
# now we have a path/cycle partition
all_part(part, iscyc)
print(f"total: {count}")
Выход для n = 2
0 1
0 0
0 0
1 0
0 1
1 0
0 0
0 0
0 0
0 1
1 0
0 0
1 0
0 1
total: 7
n=4 дает 32, как и решение, заданное hilberts_drinking_problem . n=8 дает 1441729, как и решение, заданное hilberts_drinking_problem .
Исходный ответ (неверный, поскольку рассматриваются только случаи, когда все строки равны 1)
Вот один способ решения проблемы. Во-первых, мы признаем, что любая из ваших желаемых матриц на самом деле является перестановкой строк единичной матрицы. Таким образом, нам нужно только сгенерировать все возможные перестановки из n строк и применить каждую перестановку к единичной матрице. Одним из способов создания перестановок является использование алгоритма Heap. Приведенный ниже код беззастенчиво взят из geeksforgeeks с некоторыми изменениями.
import numpy as np
def printArr(a):
print('------')
for i in range(n):
for j in range(n):
print(a[i, j],end=" ")
print()
def heapPermutation(a, size, n):
# if size becomes 1 then prints the obtained
# permutation
if (size == 1):
printArr(I[a]) # permute the rows of I
return
for i in range(size):
heapPermutation(a,size-1,n);
# if size is odd, swap first and last
# element
# else If size is even, swap ith and last element
if size&1:
a[0], a[size-1] = a[size-1],a[0]
else:
a[i], a[size-1] = a[size-1],a[i]
n = 3
I = np.identity(n, dtype=int) # use dtype=bool if that is sufficient
a = np.arange(n)
heapPermutation(a, n, n)
Результат:
------
1 0 0
0 1 0
0 0 1
------
0 1 0
1 0 0
0 0 1
------
0 0 1
1 0 0
0 1 0
------
1 0 0
0 0 1
0 1 0
------
0 1 0
0 0 1
1 0 0
------
0 0 1
0 1 0
1 0 0
Поскольку я не знаю, что вы хотите сделать с матрицы, я решил просто распечатать их, а не сохранять их (хотя для сохранения каждой из них может потребоваться много оперативной памяти при большом n).