Python: Recursively Get Permutations of 2D Array of Arrays

Question

I'm looking to recursively get all the possible permutations of a 2d array of arrays in python. For instance, the trivial case of a matrix with 2 rows would be:

test_array = [[1,2,3,4],
              [5,6,7]]
recursions = []
for a in test_array[0]:
    for b in test_array[1]:
        recursions.append([a,b])

which would output:

[[1, 5], [1, 6], [1, 7], [2, 5], [2, 6], [2, 7], [3, 5], [3, 6], [3, 7], [4, 5], [4, 6], [4, 7]]

I would like to do this for an array including arbitrarily many arrays each of arbitrary length. I'm aware of certain packages such as itertools that can do this, but I'd like to be able to do such a task myself to later extend it to a much more interesting problem.

There are many similar questions on here, such as finding permutations of a 1d array, but I've been unable to find a solution for this elsewhere.

This is NOT recursion. Recursion requires calling a function over and over and *usually* does NOT involve loops. — Rashid 'Lee' Ibrahim, Mar 19 '20 at 18:14

DarrylG · Accepted Answer · 2020-03-19T18:26:57.363

Since you don't want to use itertools, you can use a recursive function that computes the cartesian product from here

Code

def product(*seqs):
    if not seqs:
        return [[]]
    else:
        return [[x] + p for x in seqs[0] for p in product(*seqs[1:])]

Usage

product(arr1, arr2, ..., arrN)

Test 1 (unpacking test_array to individual arrays)

test_array = [[1,2,3,4],
              [5,6,7]
print(product(*test_array))

[(1, 5), (1, 6), (1, 7), (2, 5), (2, 6), (2, 7), (3, 5), (3, 6), (3, 7), (4, 5), (4, 6), (4, 7)]

Test 2 (unpacking test_array to individual arrays)

test_array = [[1,2,3,4],
          [5,6,7],
          [7,8]]
print(product(*test_array))

[(1, 5, 7), (1, 5, 8), (1, 6, 7), (1, 6, 8), (1, 7, 7), (1, 7, 8), (2, 5, 7), (2, 5, 8), (2, 6, 7), (2, 6, 8), (2, 7, 7), (2, 7, 8), (3, 5, 7), (3, 5, 8), (3, 6, 7), (3, 6, 8), (3, 7, 7), (3, 7, 8), (4, 5, 7), (4, 5, 8), (4, 6, 7), (4, 6, 8), (4, 7, 7), (4, 7,8)]

Test 3 (multiple arrays)

print(product([1, 2, 3], [4, 5], [6, 7, 8, 9]))
[[1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 6], [1, 5, 7], [1, 5, 8], [1, 5, 9], [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 6], [2, 5, 7], [2, 5, 8], [2, 5, 9], [3, 4, 6], [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 5, 6], [3, 5, 7], [3, 5, 8], [3, 5,9]]

Thank you very much! This is exactly what I needed. – Steve Mar 19 '20 at 19:38 — Steve, Mar 19 '20 at 19:38

Python: Recursively Get Permutations of 2D Array of Arrays

1 Answers1