题目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

def jiechen(x):
    n = 1
    for i in range(1,x+1):
        n = n*i
    return n

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

num = 1000000
result = ''

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

print(result)

愤怒的大头菇

a = 2701345689    #以0和1开头的数字组合有725760
b = 2798654310    #第1000000个数字a和b之间

list1 = []

for i in range(a,b):
      temp = True
      for j in range(10):
            if str(j) not in str(i):
                  temp = False
                  break
      if temp:
            list1.append(i)
     
print(list1[32319])           #第1000000个数在列表里的索引值是32319

运行结果是2783915460

愤怒的大头菇

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

jerryxjr1220

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

count = 0
for a in range(10):
        for b in range(9):
                for c in range(8):
                        for d in range(7):
                                for e in range(6):
                                        for f in range(5):
                                                for g in range(4):
                                                        for h in range(3):
                                                                for i in range(2):
                                                                        for j in range(1):
                                                                                count += 1
                                                                                if count == 1000000:
                                                                                        print (a,b,c,d,e,f,g,h,i,j)
                                                                                        a1,b1,c1,d1,e1,f1,g1,h1,i1,j1 = a,b,c,d,e,f,g,h,i,j

lst = [0,1,2,3,4,5,6,7,8,9]
final = str(lst.pop(a1))
final += str(lst.pop(b1))
final += str(lst.pop(c1))
final += str(lst.pop(d1))
final += str(lst.pop(e1))
final += str(lst.pop(f1))
final += str(lst.pop(g1))
final += str(lst.pop(h1))
final += str(lst.pop(i1))
final += str(lst.pop(j1))

print (final)

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

渡风

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

%% Problem24
% 题目24：0,1,2,3,4,5,6,7,8,9的第100万个字典排列是什么？        
function Output=Problem24(Input)
 tic
if nargin==0
     Input=1000000;
end
L=10;
Num=factorial(10);
%Num0=Num/10; %以0开头的最后一位字典排列数为[0 9 8 7 6 5 4 3 2 1],排位是362880
Num1=Num/10*2;%以1开头的最后一位字典排列数为[1 9 8 7 6 5 4 3 2 0],排位是725760
%Num2=Num/10*3;%以0开头的最后一位字典排列数为[0 9 8 7 6 5 4 3 2 1],排位是1088640
Sum=Num1;
Rank=[1 9 8 7 6 5 4 3 2 0];
while (Sum<Input)
      Rank=Dictionary_Order(Rank);
      Sum=Sum+1;
end
Result='0123456789';
for ii=1:L
    Result(ii)=num2str(Rank(ii));
end
Output=str2double(Result);
disp('此代码使用matlab编程')
disp(['Problem24所用时间为',num2str(toc),'秒'])
disp(['Problem24的答案为',num2str(Output)])
end
%% 子程序
%% Problem24
% 输入一个数组得到其下一个0字典排列的数组
function Output=Dictionary_Order(Input)
if nargin==0
Input=[1 9 8 7 6 5 4 3 2 0];
end
L=length(Input);
%1.从最右边往左边扫描，找到第一个数字符合如下标准，该数字的右邻比他大。找到坐标i
for ii=L-1:-1:1
    if Input(ii)<Input(ii+1)
         Value1=Input(ii);
         Location1=ii;
         break
    end
end
%2.从上面找到的数组下标i开始从左向右扫描，找到i右边比该数字大的元素中最小的一个。
Temp=9;
for jj=Location1+1:1:L
    if Input(jj)>Value1
       if Input(jj)<=Temp
           Temp=Input(jj);
           Value2=Input(jj);
           Location2=jj;
       end
    end
end
%3.交换两个数字
Input(Location1)=Value2;
Input(Location2)=Value1;
%4.i+1:L处逆序
Input(Location1+1:L)=fliplr(Input(Location1+1:L));
Output=Input;
end

永丨恒

result = []


def pailie(n):
    re = 1
    for i in range(n, 0, -1):
        re *= i
    return re


def findnumber(li, n):
    li = list(sorted(li))
    while True:
        tmp = pailie(len(li) - 1)
        re, mod = divmod(n, tmp)
        if mod == 0:
            if re == 0:
                for i in sorted(li, reverse=True):
                    result.append(i)
                break
            else:
                result.append(li[re - 1])
                li.remove(li[re - 1])
        else:
            result.append(li[re])
            li.remove(li[re])
        n = mod
    # return result
    return ''.join([str(k) for k in result])  # 转字符串


numbers = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
print findnumber(numbers, 1000000)

marmot

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

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

marmot

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

不到1S，应该

zengtaozt

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

小Q学Python

def f(n):
    if n == 1:
        return 1
    return n * f(n-1)

m = 1000000  # 第几个序列
w = 9  # 位数
temp = 0
i = 0
a = list('0123456789')
b = []
while True:
    if f(w) < m:
        i += 1
        m -= f(w)
        continue
    else:
        w -= 1
        b.append(a[i])
        a.remove(a[i])
        i = 0
    if w == 0 :
        break
print(''.join(b+a))

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

JAY饭

temp = [0,1,2,3,4,5,6,7,8,9]
count = []
count1 = 1
for i in range(1,10):
    count1 *= i
    count.append(count1)
count.reverse()
print(count)
# [362880, 40320, 5040, 720, 120, 24, 6, 2, 1]
#这里count的意义其实就是每往下一层所有的排列总和：
#举个栗子，以0,1,2，开头的排列每一种分别有362880种，以01或者02,03....开头的排列的分别有40320，
#以012,013，014或者其他开头的排列分别有5040种

def y(num):
    t = []
    for i in count:
        print(num//i) 
        if num%i:  #这里就是依次求出它们当前位置的数值，
            a = temp[num//i]  #比如这里如果362880%362880，说明此时排在第一位的是1，
        else:                 #如果是362879%362880，此时第一位是0，
            a = temp[num//i-1]#如果是362881%362880，此时第一位是1，第一位确定后，排除 
        temp.remove(a)        #第一位，接着计算下一个位置，而此时要排除掉排序上一位的时候总排序数，这个要意会
        num = num - (num//i)*i
        t.append(a)
    t += temp
    print(t)
y(1000000)

cwhsmile

import time
import math

def test1():
    first = '0123456789'
    count = 1
    flag = 0
    #把切片下来的字符串类型数字排序后返回，例如：'16534' ---> '13456'
    def zhengli(x):
        li = ''
        temp = list(x)
        temp.sort()
        for o in temp:
            li += o
        return li
    
    #把字符串中指定的字符移除，例如移除4：'12asf456af' --> '12asf56af'
    def syzhengli(e,f):
        s = ''
        for t in e:
            if t != f:
                s += t
        return s

    for m in range(1,1000000):
        for n in range(9,-1,-1):
            sec = first[:]
            if n == 9:
                sec = sec[:8] + sec[9] + sec[8]
                if sec > first:
                    first = sec
                    break
                else:
                    continue
            paixu = list(sec[n:])
            paixu.sort()
            for i in paixu:
                bijiao = sec[:n-1] + i + syzhengli(sec[n-1:],i)
                if not bijiao > first:
                    continue
                else:
                    first = bijiao[:n] + zhengli(bijiao[n:])
                    flag = 1
                    break
            if flag == 1:
                flag = 0
                break

    
    return first
li = []
start = time.perf_counter()
print(test1())
end = time.perf_counter()
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，报到谁，谁死，然后选定下一个报数，直到最后一个）

void getFactorial(ElementType *ans,int n){
    ElementType i = 1;
    *ans = 1;
    for(i = 2; i <= (ElementType)n; i++){
        *ans *= i;
    }
}

void test(ElementType flag, int number){
    ElementType fac;
    int index = -1;
    int i = 1;
    printf("answer is follow\n");
    while(i <= number){
        getFactorial(&fac,number-i);
        index = (int)(flag/fac);
        flag = flag % fac;
        printf("%d",index+1);
        i++;
    }
    printf("\n");
}

int main(int argc, char *argv[]){
    test(1000000-1,10);
    return 0;
}

永恒的蓝色梦想

今天不想烧脑

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

leon0149

2783915460
0.094 s

#include <stdio.h>
#include <time.h>

int main(void)
{
    clock_t start, finish;
    double duration;
    start = clock();
    int count = 0;
    for (long long i = 0; i < 10; ++i) {
        for (int j = 0; j < 10; ++j) {
            if (i != j)
            for (int k = 0; k < 10; ++k) {
                if (j != k && k != i)
                for (int l = 0; l < 10; ++l) {
                    if (k != l && l != j && l != i)
                    for (int m = 0; m < 10; ++m) {
                        if (l != m && m != k&& m != j && m != i)
                        for (int n = 0; n < 10; ++n) {
                            if (m != n && l != n && n != k && n != j && n != i)
                            for (int i1 = 0; i1 < 10; ++i1) {
                                if (n != i1 && i1!= m && i1!= k && i1!= j && i1!= i && i1!= l)
                                for (int j1 = 0; j1 < 10; ++j1) {
                                    if (i1 != j1 && m != j1 && j1!= n && j1!= k&& j1!= j && j1!= i && j1!= l)
                                    for (int k1 = 0; k1 < 10; ++k1) {
                                        if (j1 != k1 && i1 != k1 && n != k1 && k1!= m && k1!= k&& k1!= j && k1!= i && k1!= l)
                                            for (int l1 = 0; l1 < 10; ++l1) {
                                                if (l1 != k1 && j1 != l1 && i1 != l1 && n != l1 && l1!= m && l1!= k&& l1!= j && l1!= i && l1!= l)
                                                    count++;
                                                if (count == 1000000) {
                                                    printf("%lld\n", i * 1000000000 + j * 100000000 + k * 10000000 + l * 1000000 + m * 100000 + n * 10000 + i1 * 1000 + j1 * 100 + k1 * 10 + l1 * 1);
                                                    finish = clock();
                                                    duration = (double )(finish - start) / CLOCKS_PER_SEC;
                                                    printf("%.3f s", duration);
                                                    return 0;
                                                }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

debuggerzh

next_permutation强啊~

#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<queue>
#include<stack>
#include<list>
#define ICRS(i,ini,end) for (int i = ini;i < end;i++)//increase,i.e.ICS(i,0,n)
#define DCRS(i,ini,end) for (int i = ini - 1;i >= end;i--)//decrease,i.e.DCS(i,n,0)
#define MEM(x,y) memset(x,y,sizeof(x))
//#define LOCAL
#define TEST
using namespace std;
typedef long long ll;
const int M = 100 + 10;
const int INF = 1e6;
const double EPS = 1e-6;

int main(){
        #ifdef LOCAL
                freopen("i.in","r",stdin);
        #endif // LOCAL
  int a[] = {0,1,2,3,4,5,6,7,8,9};
  ICRS(i,0,INF-1){
    next_permutation(a,a+10);
  }
  ICRS(i,0,10)  cout << a[i];
        return 0;
}

有马_冬巳

'''排列是一个物体的有序安排。例如 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 万个字典排列是什么？'''

'''1. 以树状图分析，0到9 9个数字可以被分成10组，分别被视为由0到9为开头的字典排列
   2. 排列的总数通过0到1到0到4的实验可推测为数字总数的集合值
   3. 每一组的字典排列总量为排列总数的十分之一，因此可以推断第100万个字典排列的开头数字为2
   4. 后面的每一位数字都可以用这个方式来推断'''

start = time.time()

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

print("第1000000个字典排列是：")
print(dictsort)

end = time.time()
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
我一个一个打印出来了
不知道我这个哪里有问题