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

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 = 3m = 2def permutation(n, m):&nbsp; &nbsp; if n <= 0:&nbsp; &nbsp; &nbsp; &nbsp; yield []&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; for i in range(m+1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for j in permutation(n-1, m):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield [i] + j# or even shorterdef permutation(n, m):&nbsp; &nbsp; 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):&nbsp; &nbsp; 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):&nbsp; &nbsp; '''Returns a list of arrays that represent all permutations between zero&nbsp; &nbsp; and max_value'''&nbsp; &nbsp; array_member =''&nbsp; &nbsp; for_loops=''&nbsp; &nbsp; #Does a loop iteration for each member of the permutation list template&nbsp; &nbsp; for i in range(array_size):&nbsp; &nbsp; &nbsp; &nbsp; #adds a new member in each permutation&nbsp; &nbsp; &nbsp; &nbsp; array_member += f'x{i}, '&nbsp; &nbsp; &nbsp; &nbsp; #adds a new corresponding for loop&nbsp; &nbsp; &nbsp; &nbsp; for_loops+=" for x{i} in range({value})".format(i=i,&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;value=max_value)&nbsp; &nbsp; output = f'[[{array_member}] {for_loops}]' #combines it all together&nbsp; &nbsp; 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) 是你可以做到这一点的最佳时间，这就是使用迭代时得到的结果。递归也会为其内存堆栈占用更多内存。