鱼C论坛

 找回密码
 立即注册
查看: 5823|回复: 25

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

[复制链接]
发表于 2015-4-23 16:34:43 | 显示全部楼层 |阅读模式

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

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

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


评分

参与人数 2荣誉 +2 收起 理由
B1tetheDust + 1 如果你理解排列组合,只需要0.000037s
cwhsmile + 1 脑细胞烧死完了,用时5s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-8-27 19:49:17 | 显示全部楼层
  1. def jiechen(x):
  2.     n = 1
  3.     for i in range(1,x+1):
  4.         n = n*i
  5.     return n

  6. temp = [0,1,2,3,4,5,6,7,8,9]

  7. num = 1000000
  8. result = ''

  9. for i in range(9,0,-1):
  10.     b = jiechen(i)
  11.     a = temp[num//b-1]
  12.     temp.remove(a)
  13.     result = result+str(a)
  14.     num = num%b

  15. print(result)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-8-31 13:50:13 | 显示全部楼层
  1. a = 2701345689    #以0和1开头的数字组合有725760
  2. b = 2798654310    #第1000000个数字a和b之间

  3. list1 = []

  4. for i in range(a,b):
  5.       temp = True
  6.       for j in range(10):
  7.             if str(j) not in str(i):
  8.                   temp = False
  9.                   break
  10.       if temp:
  11.             list1.append(i)
  12.      
  13. print(list1[32319])           #第1000000个数在列表里的索引值是32319
复制代码

运行结果是2783915460
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-8-31 13:55:35 | 显示全部楼层
差不多需要4、5分钟的样子
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-9-20 17:36:25 | 显示全部楼层
  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. lst = [0,1,2,3,4,5,6,7,8,9]
  17. final = str(lst.pop(a1))
  18. final += str(lst.pop(b1))
  19. final += str(lst.pop(c1))
  20. final += str(lst.pop(d1))
  21. final += str(lst.pop(e1))
  22. final += str(lst.pop(f1))
  23. final += str(lst.pop(g1))
  24. final += str(lst.pop(h1))
  25. final += str(lst.pop(i1))
  26. final += str(lst.pop(j1))

  27. print (final)
复制代码


虽然代码丑,但是好处是速度快,3秒出结果。
第一行表示的是每个数字变动的次数。
第二行就根据每个数字变动的次数计算答案。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-1-22 11:23:39 | 显示全部楼层
此代码使用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
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2017-3-14 10:01:52 | 显示全部楼层
  1. result = []


  2. def pailie(n):
  3.     re = 1
  4.     for i in range(n, 0, -1):
  5.         re *= i
  6.     return re


  7. def findnumber(li, n):
  8.     li = list(sorted(li))
  9.     while True:
  10.         tmp = pailie(len(li) - 1)
  11.         re, mod = divmod(n, tmp)
  12.         if mod == 0:
  13.             if re == 0:
  14.                 for i in sorted(li, reverse=True):
  15.                     result.append(i)
  16.                 break
  17.             else:
  18.                 result.append(li[re - 1])
  19.                 li.remove(li[re - 1])
  20.         else:
  21.             result.append(li[re])
  22.             li.remove(li[re])
  23.         n = mod
  24.     # return result
  25.     return ''.join([str(k) for k in result])  # 转字符串


  26. numbers = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
  27. print findnumber(numbers, 1000000)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-17 19:04:35 | 显示全部楼层
  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-廖学峰
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2017-3-17 19:05:16 | 显示全部楼层
本帖最后由 marmot 于 2017-3-17 19:06 编辑
marmot 发表于 2017-3-17 19:04
引用廖学峰老师的itertools-廖学峰


不到1S,应该
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-6 13:44:52 | 显示全部楼层
  1. from itertools import permutations
  2. print(''.join(list(permutations('0123456789',10))[999999]))
复制代码

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-24 17:32:05 | 显示全部楼层
  1. def f(n):
  2.     if n == 1:
  3.         return 1
  4.     return n * f(n-1)

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


%time %run ol024.py
2783915460
Wall time: 3 ms
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2018-3-31 20:31:39 | 显示全部楼层
本帖最后由 JAY饭 于 2019-4-28 19:31 编辑
  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. def y(num):
  14.     t = []
  15.     for i in count:
  16.         print(num//i)
  17.         if num%i:  #这里就是依次求出它们当前位置的数值,
  18.             a = temp[num//i]  #比如这里如果362880%362880,说明此时排在第一位的是1,
  19.         else:                 #如果是362879%362880,此时第一位是0,
  20.             a = temp[num//i-1]#如果是362881%362880,此时第一位是1,第一位确定后,排除
  21.         temp.remove(a)        #第一位,接着计算下一个位置,而此时要排除掉排序上一位的时候总排序数,这个要意会
  22.         num = num - (num//i)*i
  23.         t.append(a)
  24.     t += temp
  25.     print(t)
  26. y(1000000)
复制代码

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-4-27 18:25:58 | 显示全部楼层
  1. import time
  2. import math

  3. def test1():
  4.     first = '0123456789'
  5.     count = 1
  6.     flag = 0
  7.     #把切片下来的字符串类型数字排序后返回,例如:'16534' ---> '13456'
  8.     def zhengli(x):
  9.         li = ''
  10.         temp = list(x)
  11.         temp.sort()
  12.         for o in temp:
  13.             li += o
  14.         return li
  15.    
  16.     #把字符串中指定的字符移除,例如移除4:'12asf456af' --> '12asf56af'
  17.     def syzhengli(e,f):
  18.         s = ''
  19.         for t in e:
  20.             if t != f:
  21.                 s += t
  22.         return s

  23.     for m in range(1,1000000):
  24.         for n in range(9,-1,-1):
  25.             sec = first[:]
  26.             if n == 9:
  27.                 sec = sec[:8] + sec[9] + sec[8]
  28.                 if sec > first:
  29.                     first = sec
  30.                     break
  31.                 else:
  32.                     continue
  33.             paixu = list(sec[n:])
  34.             paixu.sort()
  35.             for i in paixu:
  36.                 bijiao = sec[:n-1] + i + syzhengli(sec[n-1:],i)
  37.                 if not bijiao > first:
  38.                     continue
  39.                 else:
  40.                     first = bijiao[:n] + zhengli(bijiao[n:])
  41.                     flag = 1
  42.                     break
  43.             if flag == 1:
  44.                 flag = 0
  45.                 break

  46.    
  47.     return first
  48. li = []
  49. start = time.perf_counter()
  50. print(test1())
  51. end = time.perf_counter()
  52. print(end-start)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-4-27 18:33:54 | 显示全部楼层

看不懂你这个解法的思路,大神给小弟科普一下呗
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-4-28 19:31:46 | 显示全部楼层
cwhsmile 发表于 2019-4-27 18:33
看不懂你这个解法的思路,大神给小弟科普一下呗

已经写了注释,你可以回头看看,好久之前的答案了。都忘了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-22 17:04:37 | 显示全部楼层
本帖最后由 代号-K 于 2020-4-22 17:28 编辑

有个简单的解法,利用排序算法
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. void test(ElementType flag, int number){
  9.     ElementType fac;
  10.     int index = -1;
  11.     int i = 1;
  12.     printf("answer is follow\n");
  13.     while(i <= number){
  14.         getFactorial(&fac,number-i);
  15.         index = (int)(flag/fac);
  16.         flag = flag % fac;
  17.         printf("%d",index+1);
  18.         i++;
  19.     }
  20.     printf("\n");
  21. }

  22. int main(int argc, char *argv[]){
  23.     test(1000000-1,10);
  24.     return 0;
  25. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-5-11 19:38:50 | 显示全部楼层
今天不想烧脑
  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='')
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-5-14 15:57:44 | 显示全部楼层
2783915460
0.094 s
  1. #include <stdio.h>
  2. #include <time.h>

  3. int main(void)
  4. {
  5.     clock_t start, finish;
  6.     double duration;
  7.     start = clock();
  8.     int count = 0;
  9.     for (long long i = 0; i < 10; ++i) {
  10.         for (int j = 0; j < 10; ++j) {
  11.             if (i != j)
  12.             for (int k = 0; k < 10; ++k) {
  13.                 if (j != k && k != i)
  14.                 for (int l = 0; l < 10; ++l) {
  15.                     if (k != l && l != j && l != i)
  16.                     for (int m = 0; m < 10; ++m) {
  17.                         if (l != m && m != k&& m != j && m != i)
  18.                         for (int n = 0; n < 10; ++n) {
  19.                             if (m != n && l != n && n != k && n != j && n != i)
  20.                             for (int i1 = 0; i1 < 10; ++i1) {
  21.                                 if (n != i1 && i1!= m && i1!= k && i1!= j && i1!= i && i1!= l)
  22.                                 for (int j1 = 0; j1 < 10; ++j1) {
  23.                                     if (i1 != j1 && m != j1 && j1!= n && j1!= k&& j1!= j && j1!= i && j1!= l)
  24.                                     for (int k1 = 0; k1 < 10; ++k1) {
  25.                                         if (j1 != k1 && i1 != k1 && n != k1 && k1!= m && k1!= k&& k1!= j && k1!= i && k1!= l)
  26.                                             for (int l1 = 0; l1 < 10; ++l1) {
  27.                                                 if (l1 != k1 && j1 != l1 && i1 != l1 && n != l1 && l1!= m && l1!= k&& l1!= j && l1!= i && l1!= l)
  28.                                                     count++;
  29.                                                 if (count == 1000000) {
  30.                                                     printf("%lld\n", i * 1000000000 + j * 100000000 + k * 10000000 + l * 1000000 + m * 100000 + n * 10000 + i1 * 1000 + j1 * 100 + k1 * 10 + l1 * 1);
  31.                                                     finish = clock();
  32.                                                     duration = (double )(finish - start) / CLOCKS_PER_SEC;
  33.                                                     printf("%.3f s", duration);
  34.                                                     return 0;
  35.                                                 }
  36.                                         }
  37.                                     }
  38.                                 }
  39.                             }
  40.                         }
  41.                     }
  42.                 }
  43.             }
  44.         }
  45.     }
  46. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-7-31 17:03:41 | 显示全部楼层
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. int main(){
  27.         #ifdef LOCAL
  28.                 freopen("i.in","r",stdin);
  29.         #endif // LOCAL
  30.   int a[] = {0,1,2,3,4,5,6,7,8,9};
  31.   ICRS(i,0,INF-1){
  32.     next_permutation(a,a+10);
  33.   }
  34.   ICRS(i,0,10)  cout << a[i];
  35.         return 0;
  36. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-10-21 10:44:33 | 显示全部楼层
  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. '''1. 以树状图分析,0到9 9个数字可以被分成10组,分别被视为由0到9为开头的字典排列
  5.    2. 排列的总数通过0到1到0到4的实验可推测为数字总数的集合值
  6.    3. 每一组的字典排列总量为排列总数的十分之一,因此可以推断第100万个字典排列的开头数字为2
  7.    4. 后面的每一位数字都可以用这个方式来推断'''

  8. start = time.time()

  9. position = 1000000 #要得到的字典排列位置
  10. total = 10*9*8*7*6*5*4*3*2*1 #排列总数
  11. group = 0 #数字组的排列量
  12. location = 0 #数字推断后剩余的排列量
  13. ininum = 0 #推断出来的数字
  14. numbersequence = [0,1,2,3,4,5,6,7,8,9]
  15. dictsort = []
  16. while len(numbersequence) != 0:
  17.         group = total/len(numbersequence)
  18.         location = int(position % group)
  19.         ininum = int(position / group)
  20.         dictsort.append(numbersequence[ininum])
  21.         numbersequence.pop(ininum)
  22.         numbersequence.sort()
  23.         total = group
  24.         position = location
  25.         print(dictsort)

  26. print("第1000000个字典排列是:")
  27. print(dictsort)

  28. end = time.time()
  29. 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
我一个一个打印出来了
不知道我这个哪里有问题
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 19:30

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表