小练习：20160627 0,1,2,3,4,5,6,7,8,9的第100万个字典排列是什么

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了81道题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题，并且你每做对一题，就可以下载到参考答案的pdf文件，看看你的实现方法与参考答案有什么不同，以利于迅速提高自己的水平。

                               
登录/注册后可看大图

好了言归正传，我们开始做小练习。




题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
题目比较简单，注重程序效率和创意。
答题在一周内完成，即7.4 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。


题目：

排列是一个物体的有序安排。例如 3124 是 1, 2, 3, 4 的一种排列。如果所有的排列按照数值或者字母序排序，我们称其为一个字典序。0, 1, 2 的字典排列有：

012   021   102   120   201   210

0, 1, 2, 3, 4, 5, 6, 7, 8, 9 的第 100 万个字典排列是什么？

（即0~9的10位数从小到大的排列，可以使用itertools模块的permutations函数，但不用排列方法可以更快的得到答案，大家不妨一试）
本题将考察大家编程的效率，即用时情况。

奖励：
对所有完成程序并得出正确答案的将给予加分奖励，优秀的将额外加分。
在完成一批题目后，将根据每期的完成情况总评评出最佳，会有神秘大奖。

冬雪雪冬

我的程序如下：
就先不写注释了。大家可以看到程序优化后大幅度缩短了用时。

#方法1
import time, itertools
tt = time.time()
num = list(itertools.permutations(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'], 10))[1000000 - 1]
print('0, 1, 2, 3, 4, 5, 6, 7, 8, 9 的第 100 万个字典排列是:',''.join(num))
print('方法1用时：%.4f s'%(time.time() - tt))

#方法2
import time, itertools
tt = time.time()
num = itertools.permutations(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'], 10)
i = 1
while i < 1000000:
    next(num)
    i += 1
print('0, 1, 2, 3, 4, 5, 6, 7, 8, 9 的第 100 万个字典排列是:',''.join(next(num)))
print('方法2用时：%.4f s'%(time.time() - tt))

#方法3
import time, itertools, math
tt = time.time()
n = math.factorial(9)
num = itertools.permutations(['0', '1', '3', '4', '5', '6', '7', '8', '9'], 9)
i = 1
while i < 1000000 - n * 2:
    next(num)
    i += 1
print('0, 1, 2, 3, 4, 5, 6, 7, 8, 9 的第 100 万个字典排列是:','2' + ''.join(next(num)))
print('方法3用时：%.4f s'%(time.time() - tt))


#方法4
import time, math
tt = time.time()
n = [0 for x in range(10)]
num = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
number = 1000000 - 1
for i in range(9):
    f = math.factorial(9 - i)
    n[i] = num[number // f]
    num.pop(number // f)
    number %= f
n[9] = num[0]
print('0, 1, 2, 3, 4, 5, 6, 7, 8, 9 的第 100 万个字典排列是:',''.join(n))
print('方法4用时：%.4f s'%(time.time() - tt))

0, 1, 2, 3, 4, 5, 6, 7, 8, 9 的第 100 万个字典排列是: 2783915460
方法1用时：1.3190 s
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 的第 100 万个字典排列是: 2783915460
方法2用时：0.4110 s
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 的第 100 万个字典排列是: 2783915460
方法3用时：0.2080 s
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 的第 100 万个字典排列是: 2783915460
方法4用时：0.0080 s

wangzhenas

通过计算排列组合的情况，快速计算出排在第1000000位的数字
在i5-3210M上，计算10000次耗时0.7秒

from math import factorial as fac
from time import time

goal,total_number = 1000000,10

#to calculate the time to repeat 10000times
t = time()
for counter in range(10000):
    
    rest,num_set,result_l = goal,set(range(total_number)),list()
    for i in range(1,total_number+1):
        p = fac(total_number-i)
        for j in range(len(num_set)):
            if rest-(j+1)*p <= 0:
                result_l.append(sorted(num_set)[j])
                num_set.remove(result_l[-1])
                rest -= j*p
                break

print('result:%s'%''.join(map(str,result_l)),"time:%.3f"%(time()-t))

caobynk

def getComp(numList, n):
    import math
    numList = sorted(numList)
    result = []
    overn = 0
    for i in range(0, len(numList)):
        position = int(n/(math.factorial(len(numList)-1)))
        if position == (n/(math.factorial(len(numList)-1))):
            position -= 1
        overn = position * math.factorial(len(numList)-1)
        n -= overn
        result.append(numList[position])        
        del numList[position]
    return result

print(getComp([0,1,2,3,4,5,6,7,8,9], 1000000))

lizuolong

n=1000000-1
seq = list('0123456789')
idx = []
ret = ''
for d in range(1, len(seq)+1):
    idx = [n%d] + idx
    n //= d
for i in idx:
    ret += str(seq.pop(i))
print(ret)

答案：2783915460

还有一种思路，等下试试

这算法快很多

Spicebush

#答案为2783915460
def pl(n):
    x = n
    for i in range(1, n):
        x *= i
    return x
num = 0
ls = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
m = pl(10) - 1000000
for j in range(9):
    y = m // pl(9-j)
    m %= pl(9-j)
    num = num*10 + ls.pop(y)
num = num *10 + ls[0]
print(num)

tengfei8382

#这个函数用来创建一个数位的列表，列表中的元素分别为每增加一位数，其最大位每一个数字出现的次数。
def sort_list(number):
    list1 =[1]
    x = 1
    n = 2
    while n <= number:
        x *= n-1
        n += 1
        list1.append(x)
    list1.reverse()
    return list1

#digit参数传入多少数位的字典排序，seat_num传入需要显示哪一个位置的字典排列。
def seat(digit,seat_num):
    s_list = sort_list(digit)
    #print(s_list)#检查代码
    num_list = list(range(digit))
    #print(num_list)#检查代码
    dict_strnum = ''
    x = 0
    for n in range(digit):
        while seat_num > s_list[n]:
            seat_num -= s_list[n]
            x += 1
        else:
            dict_strnum += str(num_list[x])
            #print(dict_strnum)#检查代码
            del num_list[x]
            x = 0
    #dict_seat = int(dict_strnum)#检查代码
    return dict_strnum

x = seat(10,1000000)
print(x)

答案是2783915460

老忘

# -*- coding:Utf-8 -*-
import time
start= time.clock()

num=1000000
list=[0,1,2,3,4,5,6,7,8,9]

fact_sum=1
dict_fact={0:1}# 存放阶乘结果
for i in range(1,len(list)+1):
    fact_sum=fact_sum*i
    dict_fact[i]=fact_sum

rel_str=''# 存放结果字符串
for j in range(len(list),0,-1):
    if num>=dict_fact[j-1] and num%dict_fact[j-1]==0:
        rel_str+=str(list[int(num/dict_fact[j-1]-1)])
        list.pop(int(num/dict_fact[j-1]-1))
        if len(list)>0:
            for i in range(len(list),0,-1):
                rel_str+=str(list[i-1])
        break
    elif num>=dict_fact[j-1] and num%dict_fact[j-1]!=0:
        rel_str+=str(list[int(num/dict_fact[j-1])])
        list.pop(int(num/dict_fact[j-1]))
        num=num-dict_fact[j-1]*(int(num/dict_fact[j-1]))
    elif num<dict_fact[j-1]:
        rel_str+=str(list[0])
        list.pop(0)

print(rel_str)

end = time.clock()
print ("read: %f s" % (end - start))

结果是：2783915460

DingRan

严重支持

def next(s):
    end = True
    for i in range(len(s)-2, -1, -1):
        if s[i] < s[i+1]:
            end = False
            tmp = float('inf')
            for j in range(i, len(s)):
                if s[j] > s[i]:
                    if s[j] < tmp:
                        tmp = s[j]
                        k = j
            break
    if end == True:
        return False
    s[i], s[k] = s[k], s[i]
    sr = s[i+1:len(s)]
    sr.reverse()
    s = s[0:i+1] + sr
    return s

s = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
i = 1
while True:
    s = next(s)
    i += 1
    if i == 1000000:
        for each in s:
            print(each, end='')
        break

运行结果

>>> 
2783915460
>>> 

back0893

import itertools
a=1
temp=0
b=list(range(10))
find=False
for i in range(1,10):#固定开头，计算剩下9个的排列数
    a*=i
for i in range(10):#变换开头，计算合适超过100万
    temp+=a
    if temp>10e5 :
        temp-=a
        b=list(range(10))
        b.pop(i-1)
        for j in itertools.permutations(b):#排列可能性，合适等于100万
            temp+=1
            if temp==10e5:
                j=list(j)
                j.insert(0,i)
                print(j)
                find=True #表明发现，不在计算
                break
    if find:
        break

bacon6581

思路：
0开头，用剩下9个数进行排序，共用9！=362880种可能，且最大数为0987654321
1开头，最小的数就是1023456789，且其序列在0987654321的后一位。
1023456789 的序列为 1*9！+1=362881
2013456789 的序列为 2*9！+1=725761
3012456789 的序列为 3*9！+1=1088641
即第一位数字是“2”剩下还没用的数还有：013456789
2103456789 的序列为 2*9！+1*8！+1=766081
2701345689 的序列为 2*9！+6*8！+1=967681
2801345679 的序列为 2*9！+7*8！+1=1008001
即第二位数字是“7” 剩下还没用的数还有：01345689
...........
......

from time import time
start=time()

def jiechen(n):
    zhi=1
    while n>1:
        zhi=zhi*n
        n-=1
    return zhi

num=list(range(10))

result=0
st=''

while 1:

    n=0
    jc=jiechen(len(num)-1)

    while result+jc<1000000:
        result=result+jc
        n=n+1
    st=st+str(num.pop(n))

    if len(num)==0:
        break
print(st)
print(time()-start)

应该不会有比我速度更快了的吧！

小剑剑

import math
def quene (a,b):
      l=len(a)
      string=""
      d=math.factorial(l)
      if d<b:
            return -1
      elif d==b:
            string+=''.join(reversed(a))
            return string
      a=sorted(list(a))
      while l>1:
            d=d//l
            if d>b:
                  string+=a[0]
                  a.remove(a[0])
            elif d==b:
                  string+=a[0]+''.join(a[-1:0:-1])
                  break
            else:
                  string+=a[b//d]
                  a.remove(a[b//d])
                  b=b%d
            l-=1
      return string

print(quene("0123456789",1000000))
print(quene("abcdefghij",1000000))

>>> quene("0123456789",1000000)
'278391560'

shichaoufo

结果2783915460

import time
sta = time.time()
ys = ['0','1','2','3','4','5','6','7','8','9']
def paixu(ys):
    n=0
    for a0 in ys:
        ys.remove(a0)
        for a1 in ys:
            ys.remove(a1)
            for a2 in ys:
                ys.remove(a2)
                for a3 in ys:
                    ys.remove(a3)
                    for a4 in ys:
                        ys.remove(a4)
                        for a5 in ys:
                            ys.remove(a5)
                            for a6 in ys:
                                ys.remove(a6)
                                for a7 in ys:
                                    ys.remove(a7)
                                    for a8 in ys:
                                        n += 1
                                        if n == 1000000:
                                            ys.remove(a8)
                                            return a0+a1+a2+a3+a4+a5+a6+a7+a8+ys[0]
                                    ys.append(a7)
                                    ys.sort()
                                ys.append(a6)
                                ys.sort()
                            ys.append(a5)
                            ys.sort()
                        ys.append(a4)
                        ys.sort()
                    ys.insert(0,a3)
                    ys.sort()
                ys.insert(0,a2)
                ys.sort()
            ys.insert(0,a1)
            ys.sort()
        ys.insert(0,a0)
        ys.sort()

print("第100万个字典排列是%s" % paixu(ys))
sto = time.time()
ti = sto - sta
print("用时%f秒" % ti)

mather

先确定最高位：
10!=3628800 > 1000000
9!=362880 < 1000000
所以以0开头的共有9!个
以1开头的也有9!个
以0或1开头的共有2*9!个，所以共有725760个
以0或1或2开头的共有3*9!个这个数已经超过了1000000
所以最高位是2
算法1：

#思路是从高位到低位依次确定数字
import numpy as np
#目前还剩余的数字0~9
import datetime
starttime = datetime.datetime.now()
shengyushu = list(range(10))
#计算所有可能的阶乘1！，2！，...,10!
jishu = np.array(range(1,11))
ld = np.cumprod(jishu)
weizhi = 1000000#位置
#由高到低依次确定各位上的数字
jieguo = []
lower = 0
for i in range(9,-1,-1):#9,8,7,6,5,4,3,2,1,0
    if i==0:
        break
    for j in range(1,i+1):
        if (( lower + j * ld[i-1] <= weizhi ) and (lower + (j+1) * ld[i-1] > weizhi)):
            if lower + j*ld[i-1] < weizhi:
                jieguo.append(shengyushu.pop(j))
                lower = lower + j * ld[i-1]
            else:
                jieguo.append(shengyushu.pop(j-1))
                shengyushu.sort(reverse=True)
                jieguo.extend(shengyushu)
                break
print(jieguo)
endtime = datetime.datetime.now()
interval=(endtime - starttime)
print(interval)

作为对比，用itertools中的permutations方法求一下
算法2：

import itertools as it
import datetime
starttime = datetime.datetime.now()
index = 0
for x in it.permutations(range(10),10):
    index += 1
    if index==1000000:
        print(x)
endtime = datetime.datetime.now()
interval=(endtime - starttime)
print(interval)

结果：
[2, 7, 8, 3, 9, 1, 5, 4, 6, 0]
2783915460
用时：0:00:00.001232

洞房不败

学习

hm325800

初学Python，第一次提交小练习答案，好激动呀~~

import time
start = time.clock()


#计算阶乘
def factorial(num):
        max_order = num
        temp = range(1,num)
        for i in temp:
                max_order *= i
        return max_order

#计算倍数和余数
def s_order(max_order,order_num):
        times = order_num / max_order
        residue = order_num % max_order
        return [times,residue]


#主函数
top_num = 10
order_num = 1e6
num = list(range(top_num))
final_order = []
k =0
flag = 0


for i in num:
        if i == 0:
                max_order = [factorial(i+1)]
        else:
                max_order.append(factorial(i+1))
[times,residue] = s_order(max_order=max_order.pop(),order_num=order_num)
order_num = residue


while len(num):
        k += 1
        [times,residue] = s_order(max_order=max_order.pop(),order_num=order_num)

        order_num = residue
        if order_num == 0:

                final_order.append(num[int(times)-1])
                num.remove(num[int(times)-1])
                num.reverse()
                final_order.extend(num)
                break 
        final_order.append(num[int(times)])
        num.remove(num[int(times)])
 

print(final_order)
end = time.clock()
print ("read: %f s" % (end - start))   

输出结果
[2, 7, 8, 3, 9, 1, 5, 4, 6, 0]
read: 0.049137 s

多谢指教~~

挥舞乾坤

import itertools
n = enumerate(itertools.permutations('0123456789'),1)
for k,v in n:
    if k == 1000000:
        print(''.join(v))
        break