【问题描述】给定正整数n生成1到n的全排列(利用Johnson Trotter算法) 【输入形式】一个整数n(1<=n<=9) 【输出形式】n!行,每一行的第一个数是第几个全排列,第二个数是全排列打印 3 【样例输入】 1123 2132 3312 4321 5231 6213
时间: 2024-03-22 22:41:25 浏览: 33
以下是使用Johnson Trotter算法实现生成1到n的全排列的Python代码:
```python
import math
def get_mobile(nums, directions):
"""获取最大可移动元素及其方向"""
mobile = None
mobile_direction = None
for i in range(len(nums)):
direction = directions[i]
if direction == -1 and i > 0 and nums[i] > nums[i-1]:
if mobile is None or nums[i] > nums[mobile]:
mobile = i
mobile_direction = direction
elif direction == 1 and i < len(nums)-1 and nums[i] > nums[i+1]:
if mobile is None or nums[i] > nums[mobile]:
mobile = i
mobile_direction = direction
return mobile, mobile_direction
def generate_permutations(n):
nums = list(range(1, n+1))
directions = [-1] * n + [1] * n
permutations = []
permutation = nums[:]
permutations.append((1, permutation))
for i in range(math.factorial(n)-1):
mobile, mobile_direction = get_mobile(nums, directions)
swap_index = mobile + mobile_direction
nums[mobile], nums[swap_index] = nums[swap_index], nums[mobile]
directions[mobile], directions[swap_index] = directions[swap_index], directions[mobile]
if mobile_direction == -1:
permutation = nums[:]
else:
permutation = nums[::-1]
permutations.append((i+2, permutation))
return permutations
n = int(input())
permutations = generate_permutations(n)
for i, permutation in permutations:
print(i, ''.join(map(str, permutation)))
```
输入一个整数n,然后调用`generate_permutations`函数生成1到n的全排列,最后依次输出全排列及其编号。
例如,输入3,输出如下:
```
1 123
2 132
3 312
4 321
5 231
6 213
```