Python: Generate all permutations of a non-empty 2D array mixed with a separate list

Question

I have a matrix A:

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

And a list B:

[12, 34, 25, 9]

I want to iterate over all possible permutations that assign elements in B to the positions in A with value 0.

All nonzero elements in A must remain in their initial positions.

The number of zero-valued cells in A will never be less than the size of B. B contains only nonzero elements.

Treat each element in B as unique, but not necessarily distinct. So if two elements in B are equal, still treat the two as separate elements that must appear in A

It does not matter if an element k in B already appears in A; each permutation must place k in some zero-valued position within A.

So I'd like to iterate over these 2D arrays:

[ [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] ]

The generator must definitely include all 2D arrays that DO NOT maintain the original order of list B row-major wise.

score 1 · Answer 1 · edited Jun 20 '20 at 07:36

I think this should work. If you need something faster, I can give it a shot. The underlying idea is that your positions are actually unimportant. You're just generating the permutations and then stuffing them into the 2D array (after filtering the ones that are the same as 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);

E. Kaufman · Answer 2 · 2020-06-22T08:04:06.063

I'm directly piggy-backing off of tomaszps by converting his code into an Iterator class. I've never formally made an iterator class in Python so please feel free to critique it.

I'm still testing this code on an expensive operation, so I'm not even sure if this Iterator of mine does what I want it to. Will provide updates though:

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

--

UPDATE: This iterator of mine does not actually work as fast as I'd like it to since items produced by permutations() treats duplicate items as unique. Therefore, I'm seeing A LOT of repeat permutations as described in this StackOverflow forum

Python: Generate all permutations of a non-empty 2D array mixed with a separate list

2 Answers2