Python 整数递归排列和 returns 一组元组

Question

首先，我搜索了很多网站，并花了很多时间寻找实现这一特定要求的方法。仅举几例，来自 SO 的 this and 和来自外部站点的许多其他人。

这个要求很容易理解。

我不能使用import，只能使用递归来完成这个任务。光靠这个功能肯定能自己解决问题。不允许辅助函数。

我必须用这个定义写一个函数：

def permutation(n: int) -> set[tuple[int]]:

调用permutation(3)时的预期结果如下：

{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}

我很沮丧，我无法在这里提供任何有用的尝试。我试图为此想出一个解决方案，但想不出任何有用的东西。因此，我没有示例代码可以开始。

Answer 1

想法是，如果您可以获得 n - 1 的每个排列的列表，则可以在这些排列结果中的每个点之间插入 n。

def permutation(n):
    if n == 0:
        # base case
        return {()}
    result = set()
    for x in permutation(n - 1):
        for i in range(n):
            # insert n in position i in the permutation of all of the lesser numbers
            result.add(x[:i] + (n,) + x[i:])
    return result

Python 整数递归排列和 returns 一组元组

Python recursive permutation by integer and returns a set of tuples

python

algorithm

recursion

permutation