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 #0-9的第100万个字典排列是什么
from time import *
'''
排列是一个物体的有序安排。
例如 3124 是 1, 2, 3, 4 的一种排列。
如果所有的排列按照数值或者字母序排序，
我们称其为一个字典序。0, 1, 2 的字典排列有：
012 021 102 120 201 210
'''
p =
def next_permutation(permutation):
result = []
x = 0
y = 0
for i in range(-1, -10, -1):
if permutation < permutation:
x = permutation.index(p)
break
for i in range(-1, -10, -1):
if permutation > permutation:
y = permutation.index(p)
break
pi = permutation
permutation = permutation
permutation = 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))
python
2783915460
Time:0.0s
'''
题目：
排列是一个物体的有序安排。例如 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 万个字典排列是什么？
'''
import time
tt=time.time()
num=1000000
a='0, 1, 2, 3, 4, 5, 6, 7, 8, 9'
a=a.split(", ")
n=len(a)
# num0=num-1
# nn=1
# for i in range(1,n+1):
# nn=nn*i
# l=[]
# for i in range(n,0,-1):
# nn=nn//i
# l.append(num0//nn)
# num0=num0%nn
# print(l)
num0=num-1
l=[]
for i in range(1,n+1):
l.append(num0%i)
num0=num0//i
l=l[-1::-1]
print(l)
b=[]
for i in l:
b.append(a.pop(i))
print("".join(b))
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={0};//进行2的时候的最大值
array=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)
{
l--;
}
}
}
if(count==(k-1))//这里的k-1是第几大的意思
{
break;
}
l--;
count++;
}
printf("l是%d\n",l);
array=l;
sum=sum-title(9-i)*(k-1);//没有考虑他的初始值
//算了，考虑个鬼哦，这些是动态的且还要考虑前面已填的元素。来判断后面的大小排行0
printf("sum是%d\n",sum);
}
array=sum;
for(i=0;i<=9;i++)
{
printf("%d",array);
}
return 0;
}
/////总结，终于完成了，其中，该题的逻辑是最值得想的，弯弯曲曲，对于那些粗心大意的人是个折磨，比如我
/////逻辑点1 每次数组的赋值后，都会对后面的产生影响
/////逻辑点2 有时候单循环不足以完全判断，由于循环的前进性，无法回到前面了。 有马_冬巳 发表于 2020-10-21 10:44
你可以看我的代码，你的6哪里出错了，因为你是取余的，刚好被整除，所以定位为0，也就是此时numbersequence的最大数6，但这里是不行的，能够被整除说明了此时应当去numbersequence的第二大的数4 27839154600.001s
fn lexicographic_permutation(mut chars: Vec<u8>, mut i: u64) -> Vec<u8> {
let l = chars.len() as u64;
assert!(i < (1..=l).product::<u64>());
let c = chars.remove((i / (1..l).product::<u64>()) as usize);
i %= (1..l).product::<u64>();
if l == 1 {
assert!(i == 0);
return vec!;
}
let mut v = lexicographic_permutation(chars, i);
v.insert(0, c);
v
}
fn main() {
println!(
"{}",
String::from_utf8(lexicographic_permutation(
"0123456789".as_bytes().to_vec(),
1e6 as u64 - 1
))
.unwrap()
)
}
页:
1
[2]