Python: сгенерировать все перестановки непустого 2D-массива, смешанные с отдельным списком

Question

У меня есть матрица A:

[ [0, 1, 0]
  [6, 0, 20] 
  [0, 0, 0]
  [1, 11, 0] ]

И список B:

[12, 34, 25, 9]

Я хочу перебрать все возможные перестановки, которые присваивают элементы в B на позиции в A со значением 0.

Все ненулевые элементы в A должны оставаться на своих исходных позициях.

Количество ячеек с нулевым значением в A никогда не будет меньше размера B. B содержит только ненулевые элементы.

Считать каждый элемент в B уникальным, , но не обязательно отдельным . Поэтому, если два элемента в B равны, по-прежнему рассматривайте два как отдельные элементы, которые должны появиться в A

. Не имеет значения, присутствует ли элемент k в B уже в A; каждая перестановка должна помещать k в некоторую нулевую позицию внутри A.

Итак, я хотел бы перебрать эти 2D-массивы:

[ [12, 1, 34]
  [6, 25, 20] 
  [9, 0, 0]
  [1, 11, 0] ],

[ [12, 1, 34]
  [6, 25, 20] 
  [0, 9, 0]
  [1, 11, 0] ],
.
.
(many permutations later)
.
.
[ [0, 1, 0]
  [6, 0, 20] 
  [12, 34, 25]
  [1, 11, 9] ]

Генератор обязательно должен включать все 2D-массивы, которые НЕ поддерживают исходный порядок списка B мажорная строка мудрый.

Answer 1

Я прямо копаюсь от tomaszps, конвертируя его код в класс Iterator. Я никогда официально не создавал класс итератора в Python, поэтому, пожалуйста, не стесняйтесь его критиковать.

Я все еще тестирую этот код на дорогостоящей операции, поэтому я даже не уверен, что этот Iterator of мой делает то, что я хочу. Тем не менее, будет предоставлять обновления:

class AssignmentIterator:
    def __init__(self, A, B):
        self.A = np.array(A)
        self.B = B
    
    def __iter__(self):
        self.zero_positions = self.A == 0
        zeros = np.sum(self.zero_positions) * [0]
        substitution_list = zeros[len(self.B):] + self.B
        print(substitution_list)

        self.perms = permutations(substitution_list)
        return self

    def __next__(self):
        currentPerm = next(self.perms)
        # nonzero_part = [p for p in perm if p != 0]
        # if nonzero_part != B:
        k = 0  # Track how many elements we have put in, to make sure we're putting it at the right index.
        c = self.A.copy()
        for i, row in enumerate(self.zero_positions):
            for j, isZero in enumerate(row):
                if isZero:
                    c[i, j] = currentPerm[k]
                    k += 1
        return c

-

ОБНОВЛЕНИЕ: этот мой итератор на самом деле работает не так быстро, как хотелось бы, поскольку элементы, созданные permutations(), обрабатывают дубликаты предметы как уникальные . Поэтому я вижу МНОГО повторяющихся перестановок, как описано в этом форуме StackOverflow

Answer 2

Думаю, это должно сработать. Если вам нужно что-то быстрее, я могу попробовать. Основная идея состоит в том, что ваши позиции на самом деле не важны. Вы просто генерируете перестановки, а затем вставляете их в 2D-массив (после фильтрации тех, которые совпадают с B)

from itertools import permutations
A = np.array(A)
zero_positions = A == 0
zeros = np.sum(zero_positions) * [0]
substitution_list = zeros[len(B):] + B
perms = permutations(substitution_list)
nonzero_part = [p for p in perms if p!= 0]

results = []
for perm in perms:
    if nonzero_part != B:
        k = 0 # Track how many elements we have put in, to make sure we're putting it at the right index.
        c = A.copy()
        for i, row in enumerate(zero_positions):
            for j, elt in enumerate(row):
                if elt:        
                    c[i,j] = perm[k]
                    k += 1
        results.append(c);