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

mathtimes

有马_冬巳 发表于 2020-10-21 10:44
[2]
[2, 7]
[2, 7, 8]

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

ft215378

#0-9的第100万个字典排列是什么
from time import *
'''
排列是一个物体的有序安排。
例如 3124 是 1, 2, 3, 4 的一种排列。
如果所有的排列按照数值或者字母序排序，
我们称其为一个字典序。0, 1, 2 的字典排列有：
012   021   102   120   201   210
'''
p = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
def next_permutation(permutation):
    result = []
    x = 0
    y = 0
    for i in range(-1, -10, -1):
        if permutation[i-1] < permutation[i]:
            x = permutation.index(p[i-1])
            break
    for i in range(-1, -10, -1):
        if permutation[i] > permutation[x]:
            y = permutation.index(p[i])
            break
    pi = permutation[y]
    permutation[y] = permutation[x]
    permutation[x] = 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))

TLM

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[10]={0};//进行2的时候的最大值
        array[0]=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[n])
                                        {
                                                l--;
                                        }
                                }
                        }
                        if(count==(k-1))//这里的k-1是第几大的意思
                        {
                                break;
                        }
                        l--;
                        count++;
                }
                printf("l是%d\n",l);
                array[i]=l;
                sum=sum-title(9-i)*(k-1);//没有考虑他的初始值
                //算了，考虑个鬼哦，这些是动态的且还要考虑前面已填的元素。来判断后面的大小排行0
                printf("sum是%d\n",sum);
        }
        array[10]=sum;
        for(i=0;i<=9;i++)
        {
                printf("%d",array[i]);
        }
        return 0;
}


/////总结，终于完成了，其中，该题的逻辑是最值得想的，弯弯曲曲，对于那些粗心大意的人是个折磨，比如我

/////逻辑点1 每次数组的赋值后，都会对后面的产生影响
/////逻辑点2 有时候单循环不足以完全判断，由于循环的前进性，无法回到前面了。

叶落了

有马_冬巳 发表于 2020-10-21 10:44
[2]
[2, 7]
[2, 7, 8]

你可以看我的代码，你的6哪里出错了，因为你是取余的，刚好被整除，所以定位为0，也就是此时numbersequence的最大数6，但这里是不行的，能够被整除说明了此时应当去numbersequence的第二大的数4

mathtimes

2783915460  0.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![c];
    }
    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()
    )
}