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：

import math
def getPermutation(n, k):
    digit = [i for i in range(1, n + 1)]
    res = ""
    while n > 0:
        tmp = math.factorial(n - 1)
        idx =  (k - 1) / tmp
        k -= idx * tmp
        res += str(digit[idx])
        digit.pop(idx)
        n -= 1
    return res

冬雪雪冬

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

Futuresing

from itertools import permutations

n, k = eval(input("Enter n, k: "))

def total(n):
    total = 1
    for i in range(1, n + 1):
        total *= i
    return total
        
if n < 1 or n > 9:
    print("Invalid input！")
elif k < 0 or k > total(n):
    print("Invalid input！")
else:
    allPerm = list(permutations(range(1, n + 1), n))

permK = allPerm[k - 1]

sum = 0
for i in range(n):
    sum += permK[i] * 10 ** (n - i -1)
print(sum)

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

新学

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

jdzzj

from itertools import permutations

def fun238(n,k):
    lst=[]
    for i in range(1,n+1):
        lst.append(str(i))
    lst_new=sorted(int("".join(i)) for i in permutations(lst,n))
    return lst_new[k-1]

776667

from itertools import permutations

def fun238(n,k):
    list_n = sorted(list(permutations([i for i in range(1,n+1)])))
    return ''.join([str(i) for i in list_n[k-1]])

永恒的蓝色梦想

def func(n,k):
        from itertools import permutations as perm
        count=0
        for i in perm(range(1,n+1)):
                count+=1
                if count==k:
                        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邪神

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

import tkinter
import re
import itertools
import sys

def getnvalue():
    n=entry1.get().strip()
    return int(n)
def getkvalue():
    k=entry2.get().strip()
    return int(k)
def cal():
    output_text=''
    n=getnvalue()
    k=getkvalue()
    list1=[]
    for i in range(1,n+1):
        list1.append(i)
    list2=list(itertools.permutations(list1,n))
    for each in list2[k-1]:
        output_text+=str(each)
    text1.delete('0.0','end')
    text1.insert('end','所有排列序列：')
    outputvalue(str(list2))
    text1.insert('end','\n')
    text1.insert('end','第K个数是：')  
    outputvalue(output_text)
def outputvalue(value):
    
    text1.insert('end',value)
root=tkinter.Tk(className='每日一题238')
root.geometry='300×50+500+200'   #geometry('width×height+x+y')

label1=tkinter.Label(root,text='n')
label1.grid(row=3,column=0)
entry1=tkinter.Entry(root,bg='green')
entry1.grid(row=3,column=1)
label2=tkinter.Label(root,text='k')
label2.grid(row=3,column=2)
entry2=tkinter.Entry(root,bg='yellow')
entry2.grid(row=3,column=3)
label3=tkinter.Label(root,text='第k个排列是')
label3.grid(row=5,column=0)
text1=tkinter.Text(root,bg='white')
text1.grid(row=5,column=1,columnspan=3)
button=tkinter.Button(root,text='分析',command=cal)
button.grid()

永恒的蓝色梦想

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

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

zltzlt

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

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

这一段完全可以省去。

ouyunfu

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