相关疑难解决方法(0)

我有n个元素.为了举个例子,让我们说,7个元素,1234567.我知道有7个!=这些7个元素可能有5040个排列.

我想要一个包含两个函数的快速算法:

f(number)将0到5039之间的数字映射到唯一的排列,并且

f'(置换)将置换映射回其生成的数字.

我不关心数字和排列之间的对应关系,只要每个排列都有自己唯一的数字.

所以,举个例子,我可能会在哪里有功能

f(0) = '1234567'
f'('1234567') = 0

想到的最快的算法是枚举所有排列并在两个方向上创建查找表,这样,一旦创建表,f(0)将是O(1)并且f('1234567')将是查找字符串.然而,这是内存饥饿,特别是当n变大时.

任何人都可以提出另一种算法,它可以快速工作,没有内存缺点吗？

题

我有一个整数两个数组A[]和B[].数组B[]是固定的,我需要找到其排列A[]规则小于B[]和排列最接近的排列B[].我的意思是:

对于i in(0 <= i <n),abs(B [i] -A [i])是最小的并且A[]应该小于B[] lexiographically.

例如:

A[]={1,3,5,6,7}

B[]={7,3,2,4,6}

所以,可能最近的置换A[]来B[]的

A[]={7,3,1,6,5}

我的方法

尝试所有排列,A[]然后与之进行比较B[].但时间的复杂性将是(n! * n)

那么有什么方法可以优化这个吗？

编辑

n 可以像 10^5

为了更好地理解

我有一个定点bignumber库,想要实现快速阶乘,没有精度损失.

在纸上做了一些数学技巧后,我得到了这个公式:

(4N)!=((2N)!).((2N)!).{ (2N+1).(2N+3).(2N+5)...(4N-1) }.(2^N)/(N!)

这已经非常快了,并且通过一些编程技巧,复杂性接近~ O(log(n)).

要清楚,我目前的实现是:

//---------------------------------------------------------------------------
longnum fact(const DWORD &x,longnum &h) // h return (x>>1)! to speed up computation
    {
    if (x==0) { h=1; return  1; }
    if (x==1) { h=1; return  1; }
    if (x==2) { h=1; return  2; }
    if (x==3) { h=1; return  6; }
    if (x==4) { h=2; return 24; }
    int N4,N2,N,i; longnum c,q;
    N=(x>>2);
    N2=N<<1;
    N4=N<<2;
    h=fact(N2,q);                                          // get 2N! and N!
    c=h*h; for (i=(N2+1)|1;i<=N4;i+=2) c*=i; c/=q;         // c= …