Python: рекурсивно получить перестановки двумерного массива массивов - PullRequest
Новая
       4

Python: рекурсивно получить перестановки двумерного массива массивов

0 голосов
/ 19 марта 2020

Я рекурсивно получаю все возможные перестановки двухмерного массива в python. Например, тривиальный случай матрицы с 2 строками был бы: 

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

, который вывел бы: 

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

Я хотел бы сделать это для массива, включающего произвольно много массивов каждый произвольной длины. Мне известны некоторые пакеты, такие как itertools, которые могут это делать, но я бы хотел сам выполнить такую ​​задачу, чтобы потом расширить ее до гораздо более интересной проблемы.

Есть много похожих вопросы здесь, такие как поиск перестановок 1d массива, но я не смог найти решение для этого в другом месте.

1 Ответ

0 голосов
/ 19 марта 2020

Поскольку вы не хотите использовать itertools, вы можете использовать рекурсивную функцию, которая вычисляет декартово произведение из здесь

Код 

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

Использование 

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

Тест 1 (распаковка test_array для отдельных массивов) 

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

Тест 2 ( распаковка test_array для отдельных массивов) 

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 (несколько массивов) 

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