编写一个递归函数，输入一个正整数n并输出{1，2，…，n}[闭合]的所有置换

Question

编辑问题以包括所需的行为、特定问题或错误，以及再现问题所需的最短代码。这将帮助其他人回答这个问题。

我无法解决此任务：

编写一个递归函数，输入一个正整数n并输出所有n！{1，2，…，n}的置换。不要使用任何Sage的排列命令。使用列表存储值并使用该列表。

示例输入：3

预期输出：（1,2,3）、（1,3,2）、（2,3,1）、（2,1,3）、（3,1,2）、（3,2,1）

我在网上找到的所有东西都会生成列表的排列，而不是整数。

我想计算阶乘将有助于确定输出长度。我不知道该怎么做。请帮帮我！非常感谢。

我已经试过这个了

def per(n):
   a = []
   for i in range(n):
       for j in range(n-i):
           a.append((i, j, n-i-j-1))
   return a
per(3) 

[(0, 0, 2), (0, 1, 1), (0, 2, 0), (1, 0, 1), (1, 1, 0), (2, 0, 0)]

Answer 1

编辑：我创建了一个解决方案，它不使用任何模块，可以递归工作：

def per(n, current_perm=[], results=[], remaining=None):
    if remaining is None:
        # Create a list of all items
        remaining = list(range(1, n+1))
    if len(remaining) == 1:
        # Only one item remaining - combine with
        # current path and add to results
        current_perm.append(remaining[0])
        results.append(current_perm)
        return
    for item in remaining:
        # Create a copy of the remaining list
        # and the current_permutation
        rem = list(remaining)
        cur = list(current_perm)
        # Remove the current item from the copy
        rem.remove(item)
        # Add the item to the current path
        cur.append(item)
        per(n, cur, results, rem)
    return results

print(per(3))

输出：[[1,2,3]，[1,3,2]，[2,1,3]，[2,3,1]，[3,1,2]，[3,2,1]]

Answer 2

您可以使用回溯算法来获得排列：

def backtrack(n=None, arr=None,  i=0, out=None):
    if out is None:
        out = []
        arr = list(range(1, n + 1))
    if i == n:
        out.append(tuple(arr))
    else:
        for j in range(i, len(arr)):
            arr[i], arr[j] = arr[j], arr[i]
            backtrack(n, arr, i + 1, out)
            arr[i], arr[j] = arr[j], arr[i]
    return out

只需传入元素数：

In [18]: backtrack(3)
Out[18]: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 2, 1), (3, 1, 2)]

或使用发电机功能：

def backtrack(n=None, arr=None,  i=0):
    if arr is None:
        arr = list(range(1, n + 1))
    if i == n:
        yield (tuple(arr))
    else:
        for j in range(i, len(arr)):
            arr[i], arr[j] = arr[j], arr[i]
            yield from backtrack(n, arr, i + 1)
            arr[i], arr[j] = arr[j], arr[i]



print(list(backtrack(3)))