Python：每日一题 238（答题有奖）

zltzlt

今天的题目：

给出列表 [1,2,3,…,n]，其所有元素共有 n! 种排列。（n! 是什么？请见 https://baike.baidu.com/item/%E9%98%B6%E4%B9%98/4437932?fromtitle=n%21&fromid=7806135）

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。

提示：itertools。

示例 1:

输入: n = 3, k = 3
输出: "213"

示例 2:

输入: n = 4, k = 9
输出: "2314"

欢迎大家一起答题！

解法 1：

1. import math
   
2. def getPermutation(n, k):
   
3.     digit = [i for i in range(1, n + 1)]
   
4.     res = ""
   
5.     while n > 0:
   
6.         tmp = math.factorial(n - 1)
   
7.         idx =  (k - 1) / tmp
   
8.         k -= idx * tmp
   
9.         res += str(digit[idx])
   
10.         digit.pop(idx)
    
11.         n -= 1
    
12.     return res

复制代码

冬雪雪冬

1. import itertools
   
2. def func(n, k):
   
3.     print( *list(itertools.permutations([i for i in range(1, n + 1)], n))[k - 1], sep = '')

复制代码

Futuresing

1. from itertools import permutations
   
2. 
   
3. n, k = eval(input("Enter n, k: "))
   
4. 
   
5. def total(n):
   
6.     total = 1
   
7.     for i in range(1, n + 1):
   
8.         total *= i
   
9.     return total
   
10.         
    
11. if n < 1 or n > 9:
    
12.     print("Invalid input！")
    
13. elif k < 0 or k > total(n):
    
14.     print("Invalid input！")
    
15. else:
    
16.     allPerm = list(permutations(range(1, n + 1), n))
    
17. 
    
18. permK = allPerm[k - 1]
    
19. 
    
20. sum = 0
    
21. for i in range(n):
    
22.     sum += permK[i] * 10 ** (n - i -1)
    
23. print(sum)

复制代码

临时去学了itertools模块，还请多多指教

新学

1. >>> def fun238(n,k):
   
2.         """求由数字1~n组成的所有无重复数按升序排列后的第k个数"""
   
3.         nr = list(range(1, n+1)) # 将数字1~n存进列表，好进行组合
   
4.         max=0 # 我决定从能组合的最小数和最大数之间一个个找
   
5.         min=0
   
6.         sl = [] #存储符合要求的组合数
   
7.         for i in nr:  #组合出最小的数
   
8.                 min = min*10 + i
   
9.         for i in reversed(nr):  #组合出最大的数
   
10.                 max = max*10 + n
    
11.         for i in range(min, max+1): #从最小数遍历到最大数
    
12.                 nr.clear() #每次循环清空组成每个数的数字列表
    
13.                 j = i #开始检查，检查时需要提取每位数字会改变数值
    
14.                 while 0<j%10<=n:#每位数字必须在1~n之间
    
15.                         nr.append(j%10) #将符合条件的每位数字存进列表
    
16.                         j //= 10 #用地板除法求商
    
17.                 if len(set(numbers)) == n: #这个数必须由不同数字合成，则长度必为n
    
18.                         sl.append(i) #将符合条件的数加入列表
    
19.                
    
20.         return sl[k-1] #返回第k个数

复制代码

jdzzj

1. from itertools import permutations
   
2. 
   
3. def fun238(n,k):
   
4.     lst=[]
   
5.     for i in range(1,n+1):
   
6.         lst.append(str(i))
   
7.     lst_new=sorted(int("".join(i)) for i in permutations(lst,n))
   
8.     return lst_new[k-1]

复制代码

776667

1. from itertools import permutations
   
2. 
   
3. def fun238(n,k):
   
4.     list_n = sorted(list(permutations([i for i in range(1,n+1)])))
   
5.     return ''.join([str(i) for i in list_n[k-1]])

复制代码

永恒的蓝色梦想

1. def func(n,k):
   
2.         from itertools import permutations as perm
   
3.         count=0
   
4.         for i in perm(range(1,n+1)):
   
5.                 count+=1
   
6.                 if count==k:
   
7.                         return ''.join((str(j)for j in i)

复制代码

zltzlt

新学 发表于 2019-9-16 00:45

不错，但是超时了

zltzlt

jdzzj 发表于 2019-9-16 10:10

输入 n = 9, k = 331987 超时

zltzlt

永恒的蓝色梦想 发表于 2019-9-16 19:23

通过！
执行用时：864 ms

zltzlt

776667 发表于 2019-9-16 16:04

输入 n = 9, k = 24479 超时

lucky邪神

快下班了，细节就没有搞，都带着学

1. import tkinter
   
2. import re
   
3. import itertools
   
4. import sys
   
5. 
   
6. def getnvalue():
   
7.     n=entry1.get().strip()
   
8.     return int(n)
   
9. def getkvalue():
   
10.     k=entry2.get().strip()
    
11.     return int(k)
    
12. def cal():
    
13.     output_text=''
    
14.     n=getnvalue()
    
15.     k=getkvalue()
    
16.     list1=[]
    
17.     for i in range(1,n+1):
    
18.         list1.append(i)
    
19.     list2=list(itertools.permutations(list1,n))
    
20.     for each in list2[k-1]:
    
21.         output_text+=str(each)
    
22.     text1.delete('0.0','end')
    
23.     text1.insert('end','所有排列序列：')
    
24.     outputvalue(str(list2))
    
25.     text1.insert('end','\n')
    
26.     text1.insert('end','第K个数是：')  
    
27.     outputvalue(output_text)
    
28. def outputvalue(value):
    
29.    
    
30.     text1.insert('end',value)
    
31. root=tkinter.Tk(className='每日一题238')
    
32. root.geometry='300×50+500+200'   #geometry('width×height+x+y')
    
33. 
    
34. label1=tkinter.Label(root,text='n')
    
35. label1.grid(row=3,column=0)
    
36. entry1=tkinter.Entry(root,bg='green')
    
37. entry1.grid(row=3,column=1)
    
38. label2=tkinter.Label(root,text='k')
    
39. label2.grid(row=3,column=2)
    
40. entry2=tkinter.Entry(root,bg='yellow')
    
41. entry2.grid(row=3,column=3)
    
42. label3=tkinter.Label(root,text='第k个排列是')
    
43. label3.grid(row=5,column=0)
    
44. text1=tkinter.Text(root,bg='white')
    
45. text1.grid(row=5,column=1,columnspan=3)
    
46. button=tkinter.Button(root,text='分析',command=cal)
    
47. button.grid()

复制代码

永恒的蓝色梦想

zltzlt 发表于 2019-9-16 22:39
通过！
执行用时：864 ms

话说……如果删去数据检验是不是更快一点？

zltzlt

永恒的蓝色梦想 发表于 2019-9-17 18:42
话说……如果删去数据检验是不是更快一点？

1. from math import factorial as fact
   
2.         if k>fact(n) or\
   
3.                 not(1<=n<=9):
   
4.                 raise ValueError

复制代码

这一段完全可以省去。

ouyunfu

1. from itertools import permutations as p
   
2. def f238(n,k):
   
3.     return ''.join(list(p([str(i) for i in range(1,n+1)],n))[k-1])
   
4. print(f238(3,3))

复制代码