Ordenar elementos em uma matriz com base em outra matriz

Isso pode ser feito com um ILP (Programa Linear Inteiro). Um corte bruto é mostrado abaixo. Parece que você não declarou nenhuma ponderação para considerar um resultado superior a outro, então você também pode ter sorte com uma abordagem CP (Programação de Restrições). O ILP abaixo usa o número de preenchimentos de elementos bem-sucedidos como objetivo. Pode haver muitas soluções (ou nenhuma), e apenas pegará a primeira descoberta.

É importante notar que o exemplo que você forneceu não tem solução para uma matriz de destino 3x3. Usei o segmento abaixo para criar elementos da matriz identidade (invertida 1/0), que - por inspeção - é o melhor possível para ajustar a lista de elementos.

Ajustei adj()um pouco sua função porque você tinha um esquema misto onde pegava (x, y) e retornava uma posição numerada.... Acabei de fazer tudo (x, y)

Se houver uma solução, esta tende a encontrá-la muito rapidamente para tamanhos moderados de matrix_a, especialmente se o conjunto de soluções for grande.

Eu usei cbco solucionador aqui, que é um ótimo freeware, mas existem outros solucionadores MIP que funcionam bem (glpk, highs, ...)

Ainda há alguma "carne com osso" aqui para otimizar um pouco isso, principalmente através do corte de domínio das [e, p, a]tuplas para atribuições legais com base no avalor, o que significa que qualquer place[e, p, a]elemento em que etenha um atributo for diferente de zero anão é legal e deve ser removido do domínio para place. adjacencyEntão você pode pré-computar os possíveis vizinhos para qualquer elemento para reduzir um pouco o tamanho da restrição.

Código:

"""
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')

Saída (truncada):

((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!