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

欧拉计划

Lexicographic permutations

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 万个字典排列是什么？

Plusenxue

1. def jiechen(x):
   
2.     n = 1
   
3.     for i in range(1,x+1):
   
4.         n = n*i
   
5.     return n
   
6. 
   
7. temp = [0,1,2,3,4,5,6,7,8,9]
   
8. 
   
9. num = 1000000
   
10. result = ''
    
11. 
    
12. for i in range(9,0,-1):
    
13.     b = jiechen(i)
    
14.     a = temp[num//b-1]
    
15.     temp.remove(a)
    
16.     result = result+str(a)
    
17.     num = num%b
    
18. 
    
19. print(result)
    

复制代码

愤怒的大头菇

1. a = 2701345689    #以0和1开头的数字组合有725760
   
2. b = 2798654310    #第1000000个数字a和b之间
   
3. 
   
4. list1 = []
   
5. 
   
6. for i in range(a,b):
   
7.       temp = True
   
8.       for j in range(10):
   
9.             if str(j) not in str(i):
   
10.                   temp = False
    
11.                   break
    
12.       if temp:
    
13.             list1.append(i)
    
14.      
    
15. print(list1[32319])           #第1000000个数在列表里的索引值是32319
    

复制代码

运行结果是2783915460

愤怒的大头菇

差不多需要4、5分钟的样子

jerryxjr1220

1. 2 6 6 2 5 1 2 1 1 0
   
2. 2783915460
   
3. [Finished in 3.0s]

复制代码

1. count = 0
   
2. for a in range(10):
   
3.         for b in range(9):
   
4.                 for c in range(8):
   
5.                         for d in range(7):
   
6.                                 for e in range(6):
   
7.                                         for f in range(5):
   
8.                                                 for g in range(4):
   
9.                                                         for h in range(3):
   
10.                                                                 for i in range(2):
    
11.                                                                         for j in range(1):
    
12.                                                                                 count += 1
    
13.                                                                                 if count == 1000000:
    
14.                                                                                         print (a,b,c,d,e,f,g,h,i,j)
    
15.                                                                                         a1,b1,c1,d1,e1,f1,g1,h1,i1,j1 = a,b,c,d,e,f,g,h,i,j
    
16. 
    
17. lst = [0,1,2,3,4,5,6,7,8,9]
    
18. final = str(lst.pop(a1))
    
19. final += str(lst.pop(b1))
    
20. final += str(lst.pop(c1))
    
21. final += str(lst.pop(d1))
    
22. final += str(lst.pop(e1))
    
23. final += str(lst.pop(f1))
    
24. final += str(lst.pop(g1))
    
25. final += str(lst.pop(h1))
    
26. final += str(lst.pop(i1))
    
27. final += str(lst.pop(j1))
    
28. 
    
29. print (final)

复制代码

虽然代码丑，但是好处是速度快，3秒出结果。
第一行表示的是每个数字变动的次数。
第二行就根据每个数字变动的次数计算答案。

渡风

此代码使用matlab编程
Problem24所用时间为9.2074秒
Problem24的答案为2783915460

1. %% Problem24
   
2. % 题目24：0,1,2,3,4,5,6,7,8,9的第100万个字典排列是什么？       
   
3. function Output=Problem24(Input)
   
4. tic
   
5. if nargin==0
   
6.      Input=1000000;
   
7. end
   
8. L=10;
   
9. Num=factorial(10);
   
10. %Num0=Num/10; %以0开头的最后一位字典排列数为[0 9 8 7 6 5 4 3 2 1],排位是362880
    
11. Num1=Num/10*2;%以1开头的最后一位字典排列数为[1 9 8 7 6 5 4 3 2 0],排位是725760
    
12. %Num2=Num/10*3;%以0开头的最后一位字典排列数为[0 9 8 7 6 5 4 3 2 1],排位是1088640
    
13. Sum=Num1;
    
14. Rank=[1 9 8 7 6 5 4 3 2 0];
    
15. while (Sum<Input)
    
16.       Rank=Dictionary_Order(Rank);
    
17.       Sum=Sum+1;
    
18. end
    
19. Result='0123456789';
    
20. for ii=1:L
    
21.     Result(ii)=num2str(Rank(ii));
    
22. end
    
23. Output=str2double(Result);
    
24. disp('此代码使用matlab编程')
    
25. disp(['Problem24所用时间为',num2str(toc),'秒'])
    
26. disp(['Problem24的答案为',num2str(Output)])
    
27. end
    
28. %% 子程序
    
29. %% Problem24
    
30. % 输入一个数组得到其下一个0字典排列的数组
    
31. function Output=Dictionary_Order(Input)
    
32. if nargin==0
    
33. Input=[1 9 8 7 6 5 4 3 2 0];
    
34. end
    
35. L=length(Input);
    
36. %1.从最右边往左边扫描，找到第一个数字符合如下标准，该数字的右邻比他大。找到坐标i
    
37. for ii=L-1:-1:1
    
38.     if Input(ii)<Input(ii+1)
    
39.          Value1=Input(ii);
    
40.          Location1=ii;
    
41.          break
    
42.     end
    
43. end
    
44. %2.从上面找到的数组下标i开始从左向右扫描，找到i右边比该数字大的元素中最小的一个。
    
45. Temp=9;
    
46. for jj=Location1+1:1:L
    
47.     if Input(jj)>Value1
    
48.        if Input(jj)<=Temp
    
49.            Temp=Input(jj);
    
50.            Value2=Input(jj);
    
51.            Location2=jj;
    
52.        end
    
53.     end
    
54. end
    
55. %3.交换两个数字
    
56. Input(Location1)=Value2;
    
57. Input(Location2)=Value1;
    
58. %4.i+1:L处逆序
    
59. Input(Location1+1:L)=fliplr(Input(Location1+1:L));
    
60. Output=Input;
    
61. end

复制代码

永丨恒

1. result = []
   
2. 
   
3. 
   
4. def pailie(n):
   
5.     re = 1
   
6.     for i in range(n, 0, -1):
   
7.         re *= i
   
8.     return re
   
9. 
   
10. 
    
11. def findnumber(li, n):
    
12.     li = list(sorted(li))
    
13.     while True:
    
14.         tmp = pailie(len(li) - 1)
    
15.         re, mod = divmod(n, tmp)
    
16.         if mod == 0:
    
17.             if re == 0:
    
18.                 for i in sorted(li, reverse=True):
    
19.                     result.append(i)
    
20.                 break
    
21.             else:
    
22.                 result.append(li[re - 1])
    
23.                 li.remove(li[re - 1])
    
24.         else:
    
25.             result.append(li[re])
    
26.             li.remove(li[re])
    
27.         n = mod
    
28.     # return result
    
29.     return ''.join([str(k) for k in result])  # 转字符串
    
30. 
    
31. 
    
32. numbers = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
    
33. print findnumber(numbers, 1000000)

复制代码

marmot

1. import itertools
   
2. count = 0
   
3. for i in list(itertools.permutations([0,1,2,3,4,5,6,7,8,9])):
   
4.     count += 1
   
5.     if count == 1000000:
   
6.         print(i)
   
7.     else:
   
8.         continue

复制代码

引用廖学峰老师的itertools-廖学峰

marmot

marmot 发表于 2017-3-17 19:04
引用廖学峰老师的itertools-廖学峰

不到1S，应该

zengtaozt

1. from itertools import permutations
   
2. print(''.join(list(permutations('0123456789',10))[999999]))

复制代码

小Q学Python

1. def f(n):
   
2.     if n == 1:
   
3.         return 1
   
4.     return n * f(n-1)
   
5. 
   
6. m = 1000000  # 第几个序列
   
7. w = 9  # 位数
   
8. temp = 0
   
9. i = 0
   
10. a = list('0123456789')
    
11. b = []
    
12. while True:
    
13.     if f(w) < m:
    
14.         i += 1
    
15.         m -= f(w)
    
16.         continue
    
17.     else:
    
18.         w -= 1
    
19.         b.append(a[i])
    
20.         a.remove(a[i])
    
21.         i = 0
    
22.     if w == 0 :
    
23.         break
    
24. print(''.join(b+a))

复制代码

%time %run ol024.py
2783915460
Wall time: 3 ms

JAY饭

1. temp = [0,1,2,3,4,5,6,7,8,9]
   
2. count = []
   
3. count1 = 1
   
4. for i in range(1,10):
   
5.     count1 *= i
   
6.     count.append(count1)
   
7. count.reverse()
   
8. print(count)
   
9. # [362880, 40320, 5040, 720, 120, 24, 6, 2, 1]
   
10. #这里count的意义其实就是每往下一层所有的排列总和：
    
11. #举个栗子，以0,1,2，开头的排列每一种分别有362880种，以01或者02,03....开头的排列的分别有40320，
    
12. #以012,013，014或者其他开头的排列分别有5040种
    
13. 
    
14. def y(num):
    
15.     t = []
    
16.     for i in count:
    
17.         print(num//i)
    
18.         if num%i:  #这里就是依次求出它们当前位置的数值，
    
19.             a = temp[num//i]  #比如这里如果362880%362880，说明此时排在第一位的是1，
    
20.         else:                 #如果是362879%362880，此时第一位是0，
    
21.             a = temp[num//i-1]#如果是362881%362880，此时第一位是1，第一位确定后，排除
    
22.         temp.remove(a)        #第一位，接着计算下一个位置，而此时要排除掉排序上一位的时候总排序数，这个要意会
    
23.         num = num - (num//i)*i
    
24.         t.append(a)
    
25.     t += temp
    
26.     print(t)
    
27. y(1000000)
    

复制代码

cwhsmile

1. import time
   
2. import math
   
3. 
   
4. def test1():
   
5.     first = '0123456789'
   
6.     count = 1
   
7.     flag = 0
   
8.     #把切片下来的字符串类型数字排序后返回，例如：'16534' ---> '13456'
   
9.     def zhengli(x):
   
10.         li = ''
    
11.         temp = list(x)
    
12.         temp.sort()
    
13.         for o in temp:
    
14.             li += o
    
15.         return li
    
16.    
    
17.     #把字符串中指定的字符移除，例如移除4：'12asf456af' --> '12asf56af'
    
18.     def syzhengli(e,f):
    
19.         s = ''
    
20.         for t in e:
    
21.             if t != f:
    
22.                 s += t
    
23.         return s
    
24. 
    
25.     for m in range(1,1000000):
    
26.         for n in range(9,-1,-1):
    
27.             sec = first[:]
    
28.             if n == 9:
    
29.                 sec = sec[:8] + sec[9] + sec[8]
    
30.                 if sec > first:
    
31.                     first = sec
    
32.                     break
    
33.                 else:
    
34.                     continue
    
35.             paixu = list(sec[n:])
    
36.             paixu.sort()
    
37.             for i in paixu:
    
38.                 bijiao = sec[:n-1] + i + syzhengli(sec[n-1:],i)
    
39.                 if not bijiao > first:
    
40.                     continue
    
41.                 else:
    
42.                     first = bijiao[:n] + zhengli(bijiao[n:])
    
43.                     flag = 1
    
44.                     break
    
45.             if flag == 1:
    
46.                 flag = 0
    
47.                 break
    
48. 
    
49.    
    
50.     return first
    
51. li = []
    
52. start = time.perf_counter()
    
53. print(test1())
    
54. end = time.perf_counter()
    
55. print(end-start)

复制代码

cwhsmile

JAY饭 发表于 2018-3-31 20:31

看不懂你这个解法的思路，大神给小弟科普一下呗

JAY饭

cwhsmile 发表于 2019-4-27 18:33
看不懂你这个解法的思路，大神给小弟科普一下呗

已经写了注释，你可以回头看看，好久之前的答案了。都忘了

代号-K

有个简单的解法，利用排序算法
answer is follow
3773623221
变换 2783915460
（变换方法：从0到9，报到谁，谁死，然后选定下一个报数，直到最后一个）

1. void getFactorial(ElementType *ans,int n){
   
2.     ElementType i = 1;
   
3.     *ans = 1;
   
4.     for(i = 2; i <= (ElementType)n; i++){
   
5.         *ans *= i;
   
6.     }
   
7. }
   
8. 
   
9. void test(ElementType flag, int number){
   
10.     ElementType fac;
    
11.     int index = -1;
    
12.     int i = 1;
    
13.     printf("answer is follow\n");
    
14.     while(i <= number){
    
15.         getFactorial(&fac,number-i);
    
16.         index = (int)(flag/fac);
    
17.         flag = flag % fac;
    
18.         printf("%d",index+1);
    
19.         i++;
    
20.     }
    
21.     printf("\n");
    
22. }
    
23. 
    
24. int main(int argc, char *argv[]){
    
25.     test(1000000-1,10);
    
26.     return 0;
    
27. }

复制代码

永恒的蓝色梦想

今天不想烧脑

1. from itertools import permutations
   
2. for _,res in zip(range(1000000),permutations((0, 1, 2, 3, 4, 5, 6, 7, 8, 9))):
   
3.     pass
   
4. print(*res,sep='')

复制代码

leon0149

2783915460
0.094 s

1. #include <stdio.h>
   
2. #include <time.h>
   
3. 
   
4. int main(void)
   
5. {
   
6.     clock_t start, finish;
   
7.     double duration;
   
8.     start = clock();
   
9.     int count = 0;
   
10.     for (long long i = 0; i < 10; ++i) {
    
11.         for (int j = 0; j < 10; ++j) {
    
12.             if (i != j)
    
13.             for (int k = 0; k < 10; ++k) {
    
14.                 if (j != k && k != i)
    
15.                 for (int l = 0; l < 10; ++l) {
    
16.                     if (k != l && l != j && l != i)
    
17.                     for (int m = 0; m < 10; ++m) {
    
18.                         if (l != m && m != k&& m != j && m != i)
    
19.                         for (int n = 0; n < 10; ++n) {
    
20.                             if (m != n && l != n && n != k && n != j && n != i)
    
21.                             for (int i1 = 0; i1 < 10; ++i1) {
    
22.                                 if (n != i1 && i1!= m && i1!= k && i1!= j && i1!= i && i1!= l)
    
23.                                 for (int j1 = 0; j1 < 10; ++j1) {
    
24.                                     if (i1 != j1 && m != j1 && j1!= n && j1!= k&& j1!= j && j1!= i && j1!= l)
    
25.                                     for (int k1 = 0; k1 < 10; ++k1) {
    
26.                                         if (j1 != k1 && i1 != k1 && n != k1 && k1!= m && k1!= k&& k1!= j && k1!= i && k1!= l)
    
27.                                             for (int l1 = 0; l1 < 10; ++l1) {
    
28.                                                 if (l1 != k1 && j1 != l1 && i1 != l1 && n != l1 && l1!= m && l1!= k&& l1!= j && l1!= i && l1!= l)
    
29.                                                     count++;
    
30.                                                 if (count == 1000000) {
    
31.                                                     printf("%lld\n", i * 1000000000 + j * 100000000 + k * 10000000 + l * 1000000 + m * 100000 + n * 10000 + i1 * 1000 + j1 * 100 + k1 * 10 + l1 * 1);
    
32.                                                     finish = clock();
    
33.                                                     duration = (double )(finish - start) / CLOCKS_PER_SEC;
    
34.                                                     printf("%.3f s", duration);
    
35.                                                     return 0;
    
36.                                                 }
    
37.                                         }
    
38.                                     }
    
39.                                 }
    
40.                             }
    
41.                         }
    
42.                     }
    
43.                 }
    
44.             }
    
45.         }
    
46.     }
    
47. }

复制代码

debuggerzh

next_permutation强啊~

1. #include<sstream>
   
2. #include<iostream>
   
3. #include<cstdio>
   
4. #include<cstdlib>
   
5. #include<cmath>
   
6. #include<ctime>
   
7. #include<cstring>
   
8. #include<string>
   
9. #include<vector>
   
10. #include<set>
    
11. #include<map>
    
12. #include<algorithm>
    
13. #include<queue>
    
14. #include<stack>
    
15. #include<list>
    
16. #define ICRS(i,ini,end) for (int i = ini;i < end;i++)//increase,i.e.ICS(i,0,n)
    
17. #define DCRS(i,ini,end) for (int i = ini - 1;i >= end;i--)//decrease,i.e.DCS(i,n,0)
    
18. #define MEM(x,y) memset(x,y,sizeof(x))
    
19. //#define LOCAL
    
20. #define TEST
    
21. using namespace std;
    
22. typedef long long ll;
    
23. const int M = 100 + 10;
    
24. const int INF = 1e6;
    
25. const double EPS = 1e-6;
    
26. 
    
27. int main(){
    
28.         #ifdef LOCAL
    
29.                 freopen("i.in","r",stdin);
    
30.         #endif // LOCAL
    
31.   int a[] = {0,1,2,3,4,5,6,7,8,9};
    
32.   ICRS(i,0,INF-1){
    
33.     next_permutation(a,a+10);
    
34.   }
    
35.   ICRS(i,0,10)  cout << a[i];
    
36.         return 0;
    
37. }
    

复制代码

有马_冬巳

1. '''排列是一个物体的有序安排。例如 3124 是 1, 2, 3, 4 的一种排列。如果所有的排列按照数值或者字母序排序，我们称其为一个字典序。0, 1, 2 的字典排列有：
   
2. 012   021   102   120   201   210
   
3. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 的第 100 万个字典排列是什么？'''
   
4. 
   
5. '''1. 以树状图分析，0到9 9个数字可以被分成10组，分别被视为由0到9为开头的字典排列
   
6.    2. 排列的总数通过0到1到0到4的实验可推测为数字总数的集合值
   
7.    3. 每一组的字典排列总量为排列总数的十分之一，因此可以推断第100万个字典排列的开头数字为2
   
8.    4. 后面的每一位数字都可以用这个方式来推断'''
   
9. 
   
10. start = time.time()
    
11. 
    
12. position = 1000000 #要得到的字典排列位置
    
13. total = 10*9*8*7*6*5*4*3*2*1 #排列总数
    
14. group = 0 #数字组的排列量
    
15. location = 0 #数字推断后剩余的排列量
    
16. ininum = 0 #推断出来的数字
    
17. numbersequence = [0,1,2,3,4,5,6,7,8,9]
    
18. dictsort = []
    
19. while len(numbersequence) != 0:
    
20.         group = total/len(numbersequence)
    
21.         location = int(position % group)
    
22.         ininum = int(position / group)
    
23.         dictsort.append(numbersequence[ininum])
    
24.         numbersequence.pop(ininum)
    
25.         numbersequence.sort()
    
26.         total = group
    
27.         position = location
    
28.         print(dictsort)
    
29. 
    
30. print("第1000000个字典排列是：")
    
31. print(dictsort)
    
32. 
    
33. end = time.time()
    
34. print("共用时：%f 秒" %(end-start))

复制代码

[2]
[2, 7]
[2, 7, 8]
[2, 7, 8, 3]
[2, 7, 8, 3, 9]
[2, 7, 8, 3, 9, 1]
[2, 7, 8, 3, 9, 1, 5]
[2, 7, 8, 3, 9, 1, 5, 6]
[2, 7, 8, 3, 9, 1, 5, 6, 0]
[2, 7, 8, 3, 9, 1, 5, 6, 0, 4]
第1000000个字典排列是：
[2, 7, 8, 3, 9, 1, 5, 6, 0, 4]
共用时：0.000000 秒

看你们得到的结果都是2783915460
我一个一个打印出来了
不知道我这个哪里有问题