生成数值排列（迭代与递归）

Question

我想我正在尝试做一些非常基本和非常简单的事情。出于这个原因，我确信 Stack Overflow 已经有一个关于这个任务的 post 但我想不是吗？也许这是一个无关紧要的概念？抱歉，如果 post 已经存在。我没找到。

这是我想要完成的：给定列表长度 n 和最大元素值 m，生成所有排列列表的每个元素在 0 和 m.

之间变化

问题： 1. 有没有办法递归地做到这一点？ 2. 对于这个概念递归是最优的（在计算资源、O 时间等方面）还是迭代更好？ 3. 是否有更好的方法（更简单）使用迭代来实现此目的（请参阅下面的代码）？

更多信息见下方

我编辑了我的代码和两个示例以生成并展示完整的解决方案

这里有两个例子：

示例 1：n = 3，m = 2 输出：

[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]
[0, 2, 0]
[0, 2, 1]
[0, 2, 2]
[1, 0, 0]
[1, 0, 1]
[1, 0, 2]
[1, 1, 0]
[1, 1, 1]
[1, 1, 2]
[1, 2, 0]
[1, 2, 1]
[1, 2, 2]
[2, 0, 0]
[2, 0, 1]
[2, 0, 2]
[2, 1, 0]
[2, 1, 1]
[2, 1, 2]
[2, 2, 0]
[2, 2, 1]
[2, 2, 2]

示例 1：n = 2，m = 4 输出：

[0, 0]
[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 0]
[1, 1]
[1, 2]
[1, 3]
[1, 4]
[2, 0]
[2, 1]
[2, 2]
[2, 3]
[2, 4]
[3, 0]
[3, 1]
[3, 2]
[3, 3]
[3, 4]
[4, 0]
[4, 1]
[4, 2]
[4, 3]
[4, 4]

我的直觉告诉我这可以递归完成，但我想不出该怎么做（我是初学者程序员）。目前，我有一个迭代实现这个的解决方案：

def permute(curr_permute,max_num,reset_flgs,reset_ind):
    '''
    Increment Logic Structure
    '''
    perm_ind = 0
    max_val_flgs = [0]*len(curr_permute)
    for c_i in range(len(curr_permute)):
        if ((curr_permute[c_i] == max_num) and (c_i < (len(curr_permute)-1))):
            if ((reset_ind == c_i) and (reset_flgs[c_i] == 1)):
                reset_ind += 1
                reset_flgs[c_i] = 0
                max_val_flgs[c_i] = 1
                continue
            else:
                perm_ind += 1
                max_val_flgs[c_i] = 1
        elif (c_i == (len(curr_permute)-1)):
            if (curr_permute[c_i] == max_num):
                perm_ind = c_i
                max_val_flgs[c_i] = 1
            else:
                perm_ind = c_i
        elif (curr_permute[c_i] < max_num):
            perm_ind += 1
    '''
    Reverse the lists
    '''
    max_val_flgs.reverse()
    curr_permute.reverse()
    reset_flgs.reverse()
    '''
    Reset Logic Structure
    '''
    for n_i in range(len(curr_permute)):
        if (max_val_flgs[n_i] == 0):
            break
        elif ((max_val_flgs[n_i] == 1) and (reset_flgs[n_i] == 1)):
            curr_permute[n_i] = 0
            perm_ind += -1
    '''
    Reverse the lists
    '''
    curr_permute.reverse()
    reset_flgs.reverse()
    '''
    Apply the permutation increment
    '''
    curr_permute[perm_ind] += 1
    return(curr_permute,reset_flgs,reset_ind)

def Permutation_Generation():
    n = 2
    m = 4
   
    curr_permute = [0]*n
    reset_flgs = [1]*n
    reset_ind = 0
    All_Permutations = [list(curr_permute)]
    while (sum(curr_permute) < (n*m)):
        print(curr_permute)
        [curr_permute,reset_flgs,reset_ind] = permute(curr_permute,m,reset_flgs,reset_ind)
        All_Permutations.append(list(curr_permute))
    print(curr_permute)
    return(All_Permutations)

对垃圾代码表示歉意。一旦我想出了一个成功的方法，我就没有花太多精力去清理它或让它更有效率。我的猜测是这段代码对于我试图解决的概念来说太复杂了。

Answer 1

3. 你想得到所有的排列。给定 n 和 m 的排列数是 (m+1)^n。因为你实际上想要打印所有这些时间复杂度也是 O((m+1)^n)，这是你在迭代时得到的。

1+2. 我认为你不应该使用递归来做它，O((m+1)^n) 是你可以做的最佳时间这就是你在使用迭代时得到的。递归也将为其内存堆栈占用更多内存。

Answer 2

这个问题似乎得到了回答，但我想为迭代排列提供一个更简单的替代方案。在这里，我使用列表理解、格式化字符串文字（f'string' 字符串）和 eval built-in 方法。希望这个观点对你有所帮助（不知何故？）。

def get_permutations_list(array_size, max_value):
    '''Returns a list of arrays that represent all permutations between zero
    and max_value'''

    array_member =''
    for_loops=''

    #Does a loop iteration for each member of the permutation list template
    for i in range(array_size):

        #adds a new member in each permutation
        array_member += f'x{i}, '

        #adds a new corresponding for loop
        for_loops+=" for x{i} in range({value})".format(i=i, 
                                                   value=max_value)

    output = f'[[{array_member}] {for_loops}]' #combines it all together
    return eval(output)

a = get_permutations_list(array_size=2, max_value=2)
print(a)
#Result: [[0,0],[0,1],[1,0],[1,1]]

Answer 3

我认为您的 n 和 m 分别为 3 和 2 的输出没有意义。在第 6 行 [0, 2, 0] 之后，不是应该跟 [0, 2, 1] 而不是 [1, 0, 0] 吗？同样的情况也发生在第 13 行之后。

无论如何这是一个递归的替代方案：

n = 3
m = 2

def permutation(n, m):
    if n <= 0:
        yield []
    else:
        for i in range(m+1):
            for j in permutation(n-1, m):
                yield [i] + j

# or even shorter
def permutation(n, m):
    return [[i] + j for i in range(m + 1) for j in permutation(n - 1, m)] if n > 0 else []


for i in permutation(n, m):
    print(i)

输出：

[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 1, 0], [0, 1, 1], ..., [2, 1, 0], [2, 1, 1], [2, 1, 2], [2, 2, 0], [2, 2, 1], [2, 2, 2]]

生成数值排列（迭代与递归）

Generating Numerical Permutations (Iteration vs Recursion)

python

iteration

numeric

permutation