Как использовать рекурсию для генерации массивов в Python

Question

Я пытаюсь сгенерировать все возможные массивы со значениями от 1 до 9, используя рекурсию в python.Мой код ниже:

totalArr = []

def recursion(arr, n):
    for i in range(9):
        if (arr[i] == 0):
            arr[i] = n
            if (n < 8):
                recursion(arr, n + 1)
            else:
                print(arr)
                totalArr.append(arr)

recursion([0, 0, 0, 0, 0, 0, 0, 0, 0], 0)

print(len(totalArr))

Когда я запускаю этот код, все, что я получаю, это единственный массив ниже:

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

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

Answer 1

# Python program to print all permutations with
# duplicates allowed

# Function to print permutations of my_array
# This function takes three parameters:
# 1. my_array
# 2. Starting index of the my_array
# 3. Ending index of the my_array.
def permute(a, l, r):
    if l==r:
        print a
    else:
        for i in xrange(l,r+1):
            a[l], a[i] = a[i], a[l]
            permute(a, l+1, r)
            a[l], a[i] = a[i], a[l] # backtrack

# Driver program to test the above function
my_array = [0,1,2,3,4,5,6,7,8,9]
n = len(my_array)
a = list(my_array)
permute(a, 0, n-1)

Мы делаем перестановку с использованием рекурсии с возвратом: Подробнее о https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Answer 2

totalArr=[]
def permute(lst,n):
    ''' O(n!), optimal'''
    if n==1:totalArr.append(lst.copy())
    else:
        for i in range(n):
            lst[i],lst[n-1] = lst[n-1],lst[i]
            permute(lst,n-1)
            lst[i],lst[n-1] = lst[n-1],lst[i]
lst = [i for i in range(1,9)] # any other lst with unique elements is ok
permute(lst,len(lst))
print(totalArr)

Этот метод может генерировать все перестановки, используя алгоритм «разделяй и властвуй»