Перечисление всех возможных матриц с ограничениями

Question

Перечисление всех возможных матриц с ограничениями

Я пытаюсь перечислить все возможные матрицы размера r от r с несколькими ограничениями.

Суммы строк и столбцов должны быть в порядке возрастания.
Начиная с верхнего левого элемента вниз по главной диагонали, каждое подмножество строк и столбцов из этой записи должно состоять из комбинаций с заменами от 0 до значения в этой верхней левой записи (включительно).
Все суммы строк и столбцов должны быть меньше или равны предварительно определенному значению n.
Основная диагональ должна быть в порядке возрастания.

Важным примечанием является то, что мне нужно, чтобы каждая комбинация была где-то сохранена, или, если она написана на c ++, чтобы была выполнена другие функции после их нахождения

r а также n это значения от 2 до 100.

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

Я приложил свою последнюю попытку (которая далеко не завершена), но может дать вам представление о том, что происходит.

Функция first_section(): строит нулевую строку и нулевую колонку правильно, но кроме этого у меня ничего не получается.

Мне нужно больше, чем толчок, чтобы начать, логика — боль в заднице, и она поглощает меня целиком. Мне нужно, чтобы это было написано на Python или C ++.

import numpy as np
from itertools import combinations_with_replacement
global r
global n
r = 4
n = 8
global myarray
myarray = np.zeros((r,r))
global arraysums
arraysums = np.zeros((r,2))

def first_section():
bigData = []
myarray = np.zeros((r,r))
arraysums = np.zeros((r,2))
for i in reversed(range(1,n+1)):
myarray[0,0] = i
stuff = []
stuff = list(combinations_with_replacement(range(i),r-1))
for j in range(len(stuff)):
myarray[0,1:] = list(reversed(stuff[j]))
arraysums[0,0] = sum(myarray[0,:])
for k in range(len(stuff)):
myarray[1:,0] = list(reversed(stuff[k]))
arraysums[0,1] = sum(myarray[:,0])
if arraysums.max() > n:
break
bigData.append(np.hstack((myarray[0,:],myarray[1:,0])))
if printing: print 'myarray \n%s' %(myarray)
return bigData

def one_more_section(bigData,index):
newData = []
for item in bigData:
if printing: print 'item = %s' %(item)
upperbound = int(item[index-1])    # will need to have logic worked out
if printing: print 'upperbound = %s' % (upperbound)
for i in reversed(range(1,upperbound+1)):
myarray[index,index] = i
stuff = []
stuff = list(combinations_with_replacement(range(i),r-1))
for j in range(len(stuff)):
myarray[index,index+1:] = list(reversed(stuff[j]))
arraysums[index,0] = sum(myarray[index,:])
for k in range(len(stuff)):
myarray[index+1:,index] = list(reversed(stuff[k]))
arraysums[index,1] = sum(myarray[:,index])
if arraysums.max() > n:
break
if printing: print 'index = %s' %(index)
newData.append(np.hstack((myarray[index,index:],myarray[index+1:,index])))
if printing: print 'myarray \n%s' %(myarray)
return newData

bigData = first_section()
bigData = one_more_section(bigData,1)

Возможная матрица может выглядеть так:
r = 4, n> = 6

|3 2 0 0| = 5
|3 2 0 0| = 5
|0 0 2 1| = 3
|0 0 0 1| = 1
6 4 2 2

1

c++enumeration matrix python recursion

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Вот решение в numpy и python 2.7. Обратите внимание, что все строки и столбцы расположены в порядке возрастания, поскольку вы только указали, что они должны быть комбинациями с заменой, а не их сортировкой (а генерация комбинаций является самой простой из отсортированных списков).

Код можно несколько оптимизировать, храня суммы строк и столбцов в качестве аргументов вместо их повторного вычисления.

import numpy as np

r = 2 #matrix dimension
maxs = 5 #maximum sum of row/column

def generate(r, maxs):
# We create an extra row and column for the starting "dummy" values.
# Filling in the matrix becomes much simpler when we do not have to treat cells with
# one or two zero indices in special way. Thus, we start iteration from the
# (1, 1) index.

m = np.zeros((r + 1, r + 1), dtype = np.int32)
m[0] = m[:,0] = maxs + 1

def go(n, i, j):
# If we completely filled the matrix, yield a copy of the non-dummy parts.
if (i, j) == (r, r):
yield m[1:, 1:].copy()
return

# We compute the next indices in row major order (the choice is arbitrary).
(i2, j2) = (i + 1, 1) if j == r else (i, j + 1)

# Computing the maximum possible value for the current cell.
max_val = min(
maxs - m[i, 1:].sum(),
maxs - m[1:, j].sum(),
m[i, j-1],
m[i-1, j])

for n2 in xrange(max_val, -1, -1):
m[i, j] = n2
for matrix in go(n2, i2, j2):
yield matrix

return go(maxs, 1, 1) #note that this is a generator object

# testing
for matrix in generate(r, maxs):
print
print matrix

Если вы хотите иметь все допустимые перестановки в строках и столбцах, этот код ниже должен работать.

def generate(r, maxs):
m = np.zeros((r + 1, r + 1), dtype = np.int32)
rows = [0]*(r+1) # We avoid recomputing row/col sums on each cell.
cols = [0]*(r+1)
rows[0] = cols[0] = m[0, 0] = maxs

def go(i, j):
if (i, j) == (r, r):
yield m[1:, 1:].copy()
return

(i2, j2) = (i + 1, 1) if j == r else (i, j + 1)

max_val = min(rows[i-1] - rows[i], cols[j-1] - cols[j])

if i == j:
max_val = min(max_val, m[i-1, j-1])
if (i, j) != (1, 1):
max_val = min(max_val, m[1, 1])

for n in xrange(max_val, -1, -1):
m[i, j] = n
rows[i] += n
cols[j] += n
for matrix in go(i2, j2):
yield matrix
rows[i] -= n
cols[j] -= n

return go(1, 1)

1