PTA: 7-11 输出全排列

  • 时间:
  • 浏览:
  • 来源:互联网

7-11 输出全排列 (20 分)
请编写程序输出前n个正整数的全排列(n<10),并通过9个测试用例(即n从1到9)观察n逐步增大时程序的运行时间。

输入格式:
输入给出正整数n(<10)。

输出格式:
输出1到n的全排列。每种排列占一行,数字间无空格。排列的输出顺序为字典序,即序列a​1​​,a​2​​,⋯,a​n​​排在序列b​1​​,b​2​​,⋯,b​n​​之前,如果存在k使得a​1​​=b​1​​,⋯,a​k​​=b​k​​ 并且 a​k+1​​<b​k+1​​。

输入样例:
3

输出样例:
123
132
213
231
312
321


# 写于2021.03.21
# 本文为学习笔记,侵删
# 总结不易 望赞鼓励

方法一:随机数python版(16分)

  • 一共有sum = n!种情况
  • 那么用sum来判断找全没
  • 找全了 用seted进行排列
import random

# 首先n个数一共n!层种排列

def jieCheng(n):
    sum=1
    while(n):
        sum *= n
        n -= 1
    return  sum

n = int(input())
List = list()
Set = set()

#先用列表把1-n这几个数出现了,
for i in range(1, n+1):
    List.append(str(i))

while True:
    if len(Set) >= jieCheng(n):
        break
    #一共这么多组 当数量超过那么就是找完了
    random.shuffle(List) #随机排序
    Set.add("".join(List))
    #这里join就是把list变为字符串
    #https://blog.csdn.net/chixujohnny/article/details/53301995
answer = sorted(Set)
for i in answer:
    print(i)

缺点:速度慢 超时了有两组数据

递归 python版(18分)

依次删除每一个元素,递归求其余元素的全排列,求出其余元素全排列后,将依次删除的元素补回到最前面。

def jieCheng(n):
    sum=1
    while(n):
        sum *= n
        n -= 1
    return  sum

def permutation(lst):
    """
    python使用递归实现全排列
    """
    if len(lst)==0 or len(lst)==1:
        return [lst]
    result=[]
    for i in lst:
        temp_list=lst[:] #将lst数组赋值给temp_list
        temp_list.remove(i) #删除
        temp=permutation(temp_list) #递归生成删除一个元素后的全排列
        for j in temp: #遍历生成的全排列
            j.insert(0, i)#将删除的i添加到最前面
            result.append(j)
    return result #注意是和外层for循环对齐

n = int(input())
if n<10 and n>=1:
    numbers = list(range(1, n+1))
    sum = jieCheng(n)
    temp_result=permutation(numbers)
    for i in range(0, sum):
        c = map(str, temp_result[i])
        print("".join(c))
    
    # 通过map 把列表转换成map型,再通过join转成没有空的字符串

在这里插入图片描述
。。。。真的狗

本文链接http://www.dzjqx.cn/news/show-617085.html