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

冬雪雪冬 · 发表于 2016-6-26 21:44:44

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由冬雪雪冬于 2016-7-4 10:02 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：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函数，但不用排列方法可以更快的得到答案，大家不妨一试）
本题将考察大家编程的效率，即用时情况。

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

冬雪雪冬 · 发表于 2016-6-26 21:46:48

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

#方法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 · 发表于 2016-6-27 01:08:18

通过计算排列组合的情况，快速计算出排在第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 · 发表于 2016-6-27 08:49:14

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 · 发表于 2016-6-27 12:06:23

本帖最后由 lizuolong 于 2016-6-27 14:08 编辑

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 · 发表于 2016-6-27 18:51:39

本帖最后由 Spicebush 于 2016-6-27 19:07 编辑

#答案为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 · 发表于 2016-6-28 23:17:55

#这个函数用来创建一个数位的列表，列表中的元素分别为每增加一位数，其最大位每一个数字出现的次数。
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

老忘 · 发表于 2016-6-29 10:31:33

# -*- 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 · 发表于 2016-6-29 12:31:04

严重支持

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 · 发表于 2016-6-29 15:30:11

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 · 发表于 2016-6-29 23:16:13

本帖最后由 bacon6581 于 2016-6-30 09:05 编辑

思路：
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)

复制代码

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

小剑剑 · 发表于 2016-6-30 12:24:34

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 · 发表于 2016-6-30 15:25:07

本帖最后由 shichaoufo 于 2016-6-30 15:27 编辑

结果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 · 发表于 2016-6-30 19:17:31

本帖最后由 mather 于 2016-6-30 19:23 编辑

先确定最高位：
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

洞房不败 · 发表于 2016-7-1 17:15:15

学习

hm325800 · 发表于 2016-7-2 15:59:47

初学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

多谢指教~~

挥舞乾坤 · 发表于 2016-7-4 09:28:58

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

复制代码

账号		自动登录	找回密码
密码			立即注册

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

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分

评分

评分

评分

点评

评分

评分

评分

评分

评分

浏览过的版块