根据另一个矩阵对矩阵中的元素进行排序

这可以通过 ILP（整数线性规划）来完成。粗剪如下所示。您似乎没有声明权重来考虑一个结果优于另一个结果，因此您也可能幸运地使用 CP（约束编程）方法。下面的 ILP 使用成功元素填充的数量作为目标。可能有很多解决方案（或没有），它只会抓住第一个发现的解决方案。

值得注意的是，您提供的示例没有 3x3 目标矩阵的解决方案。我使用下面的段从单位矩阵中生成元素（翻转 1/0），通过检查，它是最适合拟合元素列表的。

我adj()稍微调整了你的函数，因为你有一个混合模式，你在其中接受 (x, y) 并返回一个编号位置......我刚刚完成了全部 (x, y)

如果存在解，对于中等大小的 ，往往会很快找到它matrix_a，特别是当解集很大时。

我cbc在这里使用了求解器，这是一个很好的免费软件，但还有其他可以正常工作的 MIP 求解器（glpk、highs，...）

这里仍然有一些“骨头上的肉”来优化这一点，主要是通过根据值将元组域修剪[e, p, a]为合法分配a，这意味着任何具有非零属性的place[e, p, a]元素都是不合法的，应该被删除来自 的域。然后，您可能会考虑预先计算任何给定元素的可能邻居，以稍微减小约束的大小。eaplaceadjacency

代码：

"""
fit elements into matrix based on adjacency rules
"""

import numpy as np
import pyomo.environ as pyo


class Element:
    """a convenience to hold the rows of attribute values"""
    def __init__(self, row):
        self.attributes = tuple(row)

    def attribute(self, idx):
        return self.attributes[idx]

    def __repr__(self):
        return str(self.attributes)


class Position:
    """a convenience for (x, y) positions that must have equality & hash defined for consistency"""
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return f'({self.x}, {self.y})'

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        if isinstance(other, Position):
            return (self.x, self.y) == (other.x, other.y)
        return False

# each 'row' corresponds to an element
# each 'column' corresponds to an attribute of the various elements
# here, each element has 5 attributes, which are always 0 or 1
element_map = np.array([[0, 0, 1, 0, 1],  # element 1
                        [1, 1, 1, 0, 1],  # element 2
                        [1, 0, 0, 1, 0],  # element 3
                        [1, 0, 1, 0, 0],  # etc.
                        [1, 1, 1, 0, 0],
                        [1, 1, 0, 1, 0],
                        [1, 0, 1, 0, 1],
                        [1, 1, 0, 0, 0],
                        [1, 1, 0, 0, 0]])  # element 9

# Alternate element map...
d = 5
element_map = np.ones((d, d), dtype=int) - np.eye(d, dtype=int)
print(element_map)

matrix_a_rows = 3
matrix_a_cols = 3
matrix_a = np.zeros((matrix_a_rows, matrix_a_cols))


def adj_xy(mat, p: Position):
    x, y = p.x, p.y
    res = []
    rows = len(mat) - 1
    cols = len(mat[0]) - 1
    for i in range(x - 1, x + 2):
        for j in range(y - 1, y + 2):
            if all((0 <= i <= rows, 0 <= j <= cols, (i, j) != (x, y))):
                res.append(Position(i, j))
    return res


# SET UP ILP
m = pyo.ConcreteModel('matrix_fitter')

# SETS

m.E = pyo.Set(initialize=[Element(row) for row in element_map], doc='elements')
m.P = pyo.Set(initialize=[Position(x, y) for x in range(len(matrix_a)) for y in range(len(matrix_a[0]))],
              doc='positions')
m.A = pyo.Set(initialize=list(range(len(element_map[0]))), doc='attribute')

# VARS
# place element e in position p based on attribute a being 0...
m.place = pyo.Var(m.E, m.P, m.A, domain=pyo.Binary, doc='place')

# OBJ:  Place as many as possible....  ideally --> len(matrix_a)
m.obj = pyo.Objective(expr=pyo.sum_product(m.place), sense=pyo.maximize)


# CONSTRAINTS
@m.Constraint(m.E, m.P, m.A)
def zero_attribute(m, e: Element, p, a):
    # can only place if attribute a is zero
    return m.place[e, p, a] * e.attribute(a) == 0


@m.Constraint(m.P)
def only_one(m, p):
    # can only place at most one element at each location
    return sum(m.place[e, p, a] for e in m.E for a in m.A) <= 1


@m.Constraint(m.E, m.P, m.A)
def adjacency(m, e: Element, p: Position, a):
    # neighbors must "add up" in the selected attribute (a), if placed in neighbor positions
    # we can "add up" the values of the selected attribute (a) for all adjacent positions that were selected
    neighbor_positions = adj_xy(matrix_a, p)
    return (sum(m.place[ee, pp, aa] * ee.attribute(a) for ee in m.E for pp in neighbor_positions for aa in m.A) >=
            len(neighbor_positions) * m.place[e, p, a])


solver = pyo.SolverFactory('cbc')
results = solver.solve(m, tee=True)
print(results)
if results.solver.termination_condition == pyo.TerminationCondition.optimal:
    for idx in m.place.index_set():
        if m.place[idx].value == 1:
            print(idx)
    if pyo.value(m.obj) == matrix_a_rows * matrix_a_cols:
        # all positions were filled
        print('success!')
    else:
        print(f'the max number of elements that can be placed is {pyo.value(m.obj)} / {matrix_a_rows * matrix_a_cols}')

else:
    print('Problem with model...see results')

输出（截断）：

((0, 1, 1, 1, 1), (0, 1), 0)
((0, 1, 1, 1, 1), (2, 1), 0)
((1, 1, 0, 1, 1), (1, 0), 2)
((1, 1, 0, 1, 1), (1, 2), 2)
((1, 1, 1, 0, 1), (1, 1), 3)
((1, 1, 1, 1, 0), (0, 0), 4)
((1, 1, 1, 1, 0), (0, 2), 4)
((1, 1, 1, 1, 0), (2, 0), 4)
((1, 1, 1, 1, 0), (2, 2), 4)
success!