如何在Python中使用递归生成数组

Question

我尝试使用python中的递归来生成所有可能的数组，其值为1-9。我的代码如下：

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

当我运行这段代码时，我得到的只是下面的一个数组：

^{pr2}$

我知道我可以对数组使用置换，但是对于这些数组的用例，我相信从长远来看递归更好。在

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)

该方法可以使用分治算法生成所有排列