首页 > 代码库 > projecteuler---->problem=24----Lexicographic permutations

projecteuler---->problem=24----Lexicographic permutations

2024-07-07 17:54:33   230人阅读

问题描述：

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

翻译：

一个排列就是物体按一定的顺序摆放。例如，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万个词法排列是……？

其实就是求全排列之后的第几个数的问题，可以转化成树的模型来做


num,s=[0,1,2,3,4,5,6,7,8,9],1
for i in range(1,11):
    s*=i
resu,length=[0]*10,0
pos=1000000    

def updataNum(n):
    for i in range(n+1,10):
        num[i-1]=num[i]

def f(sum,per,n):
    global length    
    if 10-length==1:
        return
    size = n/per
    if n%per==0:
        size-=1
    resu[length] = num[size]
    updataNum(size)
    n = n-(size)*per
    sum /= (10-length)
    per = sum/(10-length-1)
    length+=1
    f(sum, per , n)
    
f(s, s/10, pos)
resu[length]=num[0]
print resu



联系
我们