康托展开&逆展开算法笔记

时间：2023-03-09 21:31:15
康托展开&逆展开算法笔记

康托展开（有关全排列）

康托展开：已知一个排列，求这个排列在全排列中是第几个

康托展开逆运算：已知在全排列中排第几，求这个排列

定义：

X=an(n-1)!+an-1(n-2)!+...+ai(i-1)!+...+a21!+a1*0!

ai为整数，并且0<=ai<i(1<=i<=n)

简单点说就是，判断这个数在其各个数字全排列中从小到大排第几位。

比如 1 3 2，在1、2、3的全排列中排第2位。

康托展开有啥用呢？

维基：n位（0~n-1）全排列后，其康托展开唯一且最大约为n!，因此可以由更小的空间来储存这些排列。由公式可将X逆推出对应的全排列。

它可以应用于哈希表中空间压缩，而且在搜索某些类型题时，将VIS数组量压缩。比如：八数码，魔板等题

康托展开的大小即为在此排列前存在的排列的个数

比如 2 1 4 3 这个数，求其展开：

从头判断，至尾结束,

① 比 2（第一位数）小的数有多少个->1个 就是1，1*3!

② 比 1（第二位数）小的数有多少个->0个 0*2!

③ 比 4（第三位数）小的数有多少个->3个 就是1,2,3，但是1,2之前已经出现，所以是 1*1!

将所有乘积相加=7

比该数小的数有7个，所以该数排第8的位置。

1234 1243 1324 1342 1423 1432

2134 2143 2314 2341 2413 2431

3124 3142 3214 3241 3412 3421

4123 4132 4213 4231 4312 4321

//康托展开

LL Work(char str[])

{

    int len = strlen(str);

    LL ans = 0;

    for(int i=0; i<len; i++)

    {

        int tmp = 0;

        for(int j=i+1; j<len; j++)

            if(str[j] < str[i]) tmp++;

        ans += tmp * f[len-i-1];  //f[]为阶乘

    }

    return ans;  //返回该字符串是全排列中第几大，从1开始

}

逆运算的方法：

假设求4位数中第19个位置的数字。

① 19减去1 → 18

② 18 对 3! 作除法 → 得3余0

③ 0对 2! 作除法 → 得0余0

④ 0对 1! 作除法 → 得0余0

据上面的可知：

我们第一位数（最左面的数），比第一位数小的数有3个，显然 第一位数为→ 4

比第二位数小的数字有0个，所以 第二位数为→1

比第三位数小的数字有0个，因为1已经用过，所以第三位数为→2

第四位数剩下 3

该数字为 4123 (正解)

//康托逆展开

void reverse_contor(int x){

    memset(vis,0,sizeof vis);

    x--;

    int j;

    for(int i=1;i<=n;i++){

        int t=x/fac[n-i];

        for(j=1;j<=n;j++){

            if(!vis[j]){

                if(!t) break;

                t--;

            }

        }

        printf("%d ",j);

        vis[j]=1;

        x%=fac[n-i];

    }

    puts("");

}

【康托展开例题】

CSU-1828

#include<cstdio>

#include<string>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<cstring>

#include<set>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<cctype>

#include<stack>

#include<sstream>

#include<list>

#include<assert.h>

#include<bitset>

#include<numeric>

#define debug() puts("++++")

#define gcd(a,b) __gcd(a,b)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define fi first

#define se second

#define pb push_back

#define sqr(x) ((x)*(x))

#define ms(a,b) memset(a,b,sizeof(a))

#define sz size()

#define be begin()

#define mp make_pair

#define pu push_up

#define pd push_down

#define cl clear()

#define lowbit(x) -x&x

#define all 1,n,1

#define rep(i,x,n) for(int i=(x); i<(n); i++)

#define reps(i,x,n) for(int i=(x); i<=(n); i++)

#define sf scanf

#define pf printf

#define in freopen("in.in","r",stdin)

#define out freopen("out.out","w",stdout)

using namespace std;

typedef long long ll;

typedef unsigned long long ULL;

typedef pair<int,int> P;

const ULL base = 100000007;//33951943

const int INF = 0x3f3f3f3f;

const ll LNF = 9997;

const int maxn = 1e5+50;

const int maxm = 1e5 + 10;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int dx[] = {-1,1,0,0,1,1,-1,-1};

const int dy[] = {0,0,1,-1,1,-1,1,-1};

int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};

const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

ll fac[11];

char s[10];

int n,m,p;

int main()

{

	int T;

	fac[1]=1;

	rep(i,2,10) fac[i]=fac[i-1]*i;

	sf("%d",&T);

	while(T--)

    {

        sf("%s",s);

        ll res=0;

        rep(i,0,9)

        {

            ll tmp=0;

            rep(j,i+1,9)

            {

                if(s[j]<s[i]) tmp++;

            }

            res+=tmp*fac[9-i-1];

        }

        pf("%lld\n",res+1);

    }

	return 0;

}

/*

【题意】

【类型】

【分析】

【时间复杂度&&优化】

【trick】

【数据】

*/

相关文章