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

冬雪雪冬

原帖子： http://bbs.fishc.com/thread-73271-1-1.html
题目：

排列是一个物体的有序安排。例如 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函数，但不用排列方法可以更快的得到答案，大家不妨一试）
本题将考察大家编程的效率，即用时情况。


本题正确答案是：2783915460
答案正确鱼油：
wangzhenas  0.009s
caobynk  0.006s
lizuolong  0.006s
Spicebush  0.006s
tengfei8382  0.006s
老忘  0.007s
DingRan  4.025s
back0893  0.134s
bacon6581  0.006s
shichaoufo  0.648s
mather  0.1056s（算法1）
hm325800  0.323s
挥舞乾坤  0.306s

从用时比较，优秀的鱼油是：wangzhenas  0.009s
caobynk  0.006s
lizuolong  0.006s
Spicebush  0.006s
tengfei8382  0.006s
老忘  0.007s
bacon6581  0.006s

wangzhenas

楼主您好，我那个是计算1万次的时间，因为一次时间太短显示不出来，我直接就循环了一万次

冬雪雪冬

wangzhenas 发表于 2016-7-4 19:59
楼主您好，我那个是计算1万次的时间，因为一次时间太短显示不出来，我直接就循环了一万次

我弄错了，马上改。

太空军校生

能分享代码参考下吗？

冬雪雪冬

太空军校生 发表于 2016-7-5 09:17
能分享代码参考下吗？

原帖子： http://bbs.fishc.com/thread-73271-1-1.html 中有大家写的程序。

mather

为毛在我电脑上都是很少时间就出结果了，在你那要多出好多时间啊？

mather

mather 发表于 2016-7-5 10:32
为毛在我电脑上都是很少时间就出结果了，在你那要多出好多时间啊？

你是不是运行的算法2的程序啊？我用一台5年前的破笔记本也很快出结果啊~~

冬雪雪冬

mather 发表于 2016-7-5 10:32
为毛在我电脑上都是很少时间就出结果了，在你那要多出好多时间啊？

我在我办公室的计算机又算了几遍，的确在0.00x秒，不知是不是我家里计算机的numpy模块有问题，等回家再看看。

mather

冬雪雪冬 发表于 2016-7-5 10:50
我在我办公室的计算机又算了几遍，的确在0.00x秒，不知是不是我家里计算机的numpy模块有问题，等回家再看 ...

好滴~~辛苦啦~~继续支持我们的欧拉计划~~很赞！

冬雪雪冬

mather 发表于 2016-7-5 10:57
好滴~~辛苦啦~~继续支持我们的欧拉计划~~很赞！

很是奇怪，为了统一比较，我对每个人的程序都是用time函数来测定用时的，所以把你的程序中datetime部分删除掉了，如果把测时起点放在import numpy之前，用时就长的多，还是0.1s，如果放在numpy之后就只有0.008s了。

import time
tt = time.time()
#思路是从高位到低位依次确定数字
import numpy as np
#目前还剩余的数字0~9

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)

print(time.time() - tt)

[2, 7, 8, 3, 9, 1, 5, 4, 6, 0]
0.1021735668182373

#思路是从高位到低位依次确定数字
import numpy as np
#目前还剩余的数字0~9
import time
tt = time.time()
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)

print(time.time() - tt)

[2, 7, 8, 3, 9, 1, 5, 4, 6, 0]
0.008064031600952148

难道调用numpy需要很长的时间？

mather

冬雪雪冬 发表于 2016-7-5 23:38
很是奇怪，为了统一比较，我对每个人的程序都是用time函数来测定用时的，所以把你的程序中datetime部分 ...

哦，可能你的环境和我的不太一样。我这里因为主要做科学运算的，所以python环境我是用anaconda直接安装的，内置的科学运算包可能加载快一些。
没事儿的，我以后尽量不用科学计算包~

wstxh

为什么每次时间都会有很大的差异啊，而且你的时间感觉好短啊

back0893

居然有我。。我没想到