题目24：0,1,2,3,4,5,6,7,8,9的第100万个字典排列是什么？
Lexicographic permutationsA 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 万个字典排列是什么？
def jiechen(x):
n = 1
for i in range(1,x+1):
n = n*i
return n
temp =
num = 1000000
result = ''
for i in range(9,0,-1):
b = jiechen(i)
a = temp
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) #第1000000个数在列表里的索引值是32319
运行结果是2783915460 差不多需要4、5分钟的样子 2 6 6 2 5 1 2 1 1 0
2783915460
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 =
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开头的最后一位字典排列数为,排位是362880
Num1=Num/10*2;%以1开头的最后一位字典排列数为,排位是725760
%Num2=Num/10*3;%以0开头的最后一位字典排列数为,排位是1088640
Sum=Num1;
Rank=;
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=;
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)
li.remove(li)
else:
result.append(li)
li.remove(li)
n = mod
# return result
return ''.join()# 转字符串
numbers = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
print findnumber(numbers, 1000000) import itertools
count = 0
for i in list(itertools.permutations()):
count += 1
if count == 1000000:
print(i)
else:
continue
引用廖学峰老师的itertools-廖学峰 本帖最后由 marmot 于 2017-3-17 19:06 编辑
marmot 发表于 2017-3-17 19:04
引用廖学峰老师的itertools-廖学峰
不到1S，应该 from itertools import permutations
print(''.join(list(permutations('0123456789',10))))
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)
a.remove(a)
i = 0
if w == 0 :
break
print(''.join(b+a))
%time %run ol024.py
2783915460
Wall time: 3 ms 本帖最后由 JAY饭 于 2019-4-28 19:31 编辑
temp =
count = []
count1 = 1
for i in range(1,10):
count1 *= i
count.append(count1)
count.reverse()
print(count)
#
#这里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#比如这里如果362880%362880，说明此时排在第一位的是1，
else: #如果是362879%362880，此时第一位是0，
a = temp#如果是362881%362880，此时第一位是1，第一位确定后，排除
temp.remove(a) #第一位，接着计算下一个位置，而此时要排除掉排序上一位的时候总排序数，这个要意会
num = num - (num//i)*i
t.append(a)
t += temp
print(t)
y(1000000)
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 + sec
if sec > first:
first = sec
break
else:
continue
paixu = list(sec)
paixu.sort()
for i in paixu:
bijiao = sec[:n-1] + i + syzhengli(sec,i)
if not bijiao > first:
continue
else:
first = bijiao[:n] + zhengli(bijiao)
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) JAY饭 发表于 2018-3-31 20:31
看不懂你这个解法的思路，大神给小弟科普一下呗 cwhsmile 发表于 2019-4-27 18:33
看不懂你这个解法的思路，大神给小弟科普一下呗
已经写了注释，你可以回头看看，好久之前的答案了。都忘了 本帖最后由 代号-K 于 2020-4-22 17:28 编辑
有个简单的解法，利用排序算法
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;
} 今天不想烧脑{:10_256:}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='') 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;
}
}
}
}
}
}
}
}
}
}
}
} 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;
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 =
dictsort = []
while len(numbersequence) != 0:
group = total/len(numbersequence)
location = int(position % group)
ininum = int(position / group)
dictsort.append(numbersequence)
numbersequence.pop(ininum)
numbersequence.sort()
total = group
position = location
print(dictsort)
print("第1000000个字典排列是：")
print(dictsort)
end = time.time()
print("共用时：%f 秒" %(end-start))
第1000000个字典排列是：
共用时：0.000000 秒
看你们得到的结果都是2783915460
我一个一个打印出来了
不知道我这个哪里有问题
页:
[1]
2