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

mathtimes

有马_冬巳 发表于 2020-10-21 10:44
[2]
[2, 7]
[2, 7, 8]

1000000 = 9!*2+8!*6+7!*6+6!*2+5!*5+4!*1+3!*2+2!*2+1!*0+0!*0
但它自己本身(0 1 2 3 4 5 6 7 8 9)还占一种,所以
1000000 - 1 = 999999 = 9!*2+8!*6+7!*6+6!*2+5!*5+4!*1+3!*2+2!*1+1!*1+0!*0

ft215378

#0-9的第100万个字典排列是什么
from time import *
'''
排列是一个物体的有序安排。
例如 3124 是 1, 2, 3, 4 的一种排列。
如果所有的排列按照数值或者字母序排序，
我们称其为一个字典序。0, 1, 2 的字典排列有：
012   021   102   120   201   210
'''
p = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
def next_permutation(permutation):
    result = []
    x = 0
    y = 0
    for i in range(-1, -10, -1):
        if permutation[i-1] < permutation[i]:
            x = permutation.index(p[i-1])
            break
    for i in range(-1, -10, -1):
        if permutation[i] > permutation[x]:
            y = permutation.index(p[i])
            break
    pi = permutation[y]
    permutation[y] = permutation[x]
    permutation[x] = pi
    pi = permutation[(x+1):]
    pi.sort()
    result = permutation[:(x+1)] + pi
    #print(result)
    return result

num = 0
start = time()
while True:
    p = next_permutation(p)
    num += 1
    if num == 1000000:
        break
end = time()
print(p)
print("用时:%d s" % (end-start))

TLM

python
2783915460
Time:0.0s

1. '''
   
2. 题目：
   
3. 排列是一个物体的有序安排。例如 3124 是 1, 2, 3, 4 的一种排列。
   
4. 如果所有的排列按照数值或者字母序排序，我们称其为一个字典序。0, 1, 2 的字典排列有：
   
5. 012   021   102   120   201   210
   
6. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 的第 100 万个字典排列是什么？
   
7. '''
   
8. import time
   
9. tt=time.time()
   
10. num=1000000
    
11. a='0, 1, 2, 3, 4, 5, 6, 7, 8, 9'
    
12. a=a.split(", ")
    
13. n=len(a)
    
14. 
    
15. # num0=num-1
    
16. # nn=1
    
17. # for i in range(1,n+1):
    
18. #     nn=nn*i
    
19. # l=[]
    
20. # for i in range(n,0,-1):
    
21. #     nn=nn//i
    
22. #     l.append(num0//nn)
    
23. #     num0=num0%nn
    
24. # print(l)
    
25. 
    
26. num0=num-1
    
27. l=[]
    
28. for i in range(1,n+1):
    
29.     l.append(num0%i)
    
30.     num0=num0//i
    
31. l=l[-1::-1]
    
32. print(l)
    
33. 
    
34. b=[]
    
35. for i in l:
    
36.     b.append(a.pop(i))
    
37. print("".join(b))
    
38. print('Time:{}s'.format(time.time()-tt))

复制代码

最后一个for循环感觉不是很优雅。列表的pop(i)消耗比较大，但我想不出更好的办法

叶落了

#include<stdio.h>
int title(int i)
{
        int sum=1;
        int k;
        for(k=1;k<=i;k++)
        {
                sum=sum*k;
        }
        return sum;
}
int main(void)
{
        int array[10]={0};//进行2的时候的最大值
        array[0]=2;
        int i,k,n,m,l=1;
        int count;
        int s=1000000;
        int sum=title(9)*3-s;
        //printf("%d\n",sum);
        for(i=1;i<9;i++)
        {
                for(k=1;k<=8;k++)
                {
                        if(title(9-i)*k>sum)
                        {
                                break;
                        }
                }
                printf("k是%d\n",k);
                l=9;//首先考虑9为最大
                count=0;
                while(l)//进行遍历
                {
                        for(m=0;m<9;m++)
                        {
                                for(n=0;n<=9;n++)//之所以双重循环，是因为会漏，比如l=8时，前面有7，你减了之后回不去了，无法排除7.
                                {
                                        if(l==array[n])
                                        {
                                                l--;
                                        }
                                }
                        }
                        if(count==(k-1))//这里的k-1是第几大的意思
                        {
                                break;
                        }
                        l--;
                        count++;
                }
                printf("l是%d\n",l);
                array[i]=l;
                sum=sum-title(9-i)*(k-1);//没有考虑他的初始值
                //算了，考虑个鬼哦，这些是动态的且还要考虑前面已填的元素。来判断后面的大小排行0
                printf("sum是%d\n",sum);
        }
        array[10]=sum;
        for(i=0;i<=9;i++)
        {
                printf("%d",array[i]);
        }
        return 0;
}


/////总结，终于完成了，其中，该题的逻辑是最值得想的，弯弯曲曲，对于那些粗心大意的人是个折磨，比如我

/////逻辑点1 每次数组的赋值后，都会对后面的产生影响
/////逻辑点2 有时候单循环不足以完全判断，由于循环的前进性，无法回到前面了。

叶落了

有马_冬巳 发表于 2020-10-21 10:44
[2]
[2, 7]
[2, 7, 8]

你可以看我的代码，你的6哪里出错了，因为你是取余的，刚好被整除，所以定位为0，也就是此时numbersequence的最大数6，但这里是不行的，能够被整除说明了此时应当去numbersequence的第二大的数4

mathtimes

2783915460  0.001s

1. fn lexicographic_permutation(mut chars: Vec<u8>, mut i: u64) -> Vec<u8> {
   
2.     let l = chars.len() as u64;
   
3.     assert!(i < (1..=l).product::<u64>());
   
4.     let c = chars.remove((i / (1..l).product::<u64>()) as usize);
   
5.     i %= (1..l).product::<u64>();
   
6.     if l == 1 {
   
7.         assert!(i == 0);
   
8.         return vec![c];
   
9.     }
   
10.     let mut v = lexicographic_permutation(chars, i);
    
11.     v.insert(0, c);
    
12.     v
    
13. }
    
14. 
    
15. fn main() {
    
16.     println!(
    
17.         "{}",
    
18.         String::from_utf8(lexicographic_permutation(
    
19.             "0123456789".as_bytes().to_vec(),
    
20.             1e6 as u64 - 1
    
21.         ))
    
22.         .unwrap()
    
23.     )
    
24. }

复制代码