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

Question

我想我正在尝试做一些非常基本且非常简单的事情。出于这个原因，我确信 Stack Overflow 上已经有一篇关于此任务的帖子，但我想不会吧？也许这是一个无关紧要的概念？如果相关帖子已经存在，我们深表歉意。我找不到它。这是我想要完成的任务：给定列表长度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]我的直觉告诉我这可以递归地完成，但我想不出如何做到这一点（我是一名初学者程序员）。对垃圾代码表示歉意。一旦我想出了一种成功的方法，我就没有花太多精力去清理它或提高它的效率。我的猜测是这段代码对于我试图解决的概念来说太复杂了。

Answer 1

我不认为你的 n 和 m 的输出分别是 3, 2，真的有意义。在第6行之后，后面[0, 2, 0]不应该接代替吗？第 13 排之后也发生了同样的情况。[0, 2, 1][1, 0, 0]

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

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

Answer 2

这个问题似乎得到了解答，但我想为迭代排列提供一个更简单的替代方案。在这里，我使用列表推导式、格式化字符串文字（f'string' 字符串）和 eval 内置方法。希望这个观点对你有帮助（以某种方式？）。

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

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

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