1

我试图r通过r一些约束来枚举所有可能的大小矩阵。

  1. 行和列的总和必须按非升序排列。
  2. 从主对角线下方的左上角元素开始，该条目的每个行和列子集都必须由从 0 到该左上角条目（包括）中的值的替换组合组成。
  3. 行和列的总和必须都小于或等于预定的 n 值。
  4. 主对角线必须按非升序排列。

重要说明是，我需要将每个组合存储在某个地方，或者如果用 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
4

1 回答 1

1

这是 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)
于 2013-06-10T22:09:11.940 回答