【算法】康托展开和逆康托展开

你的名字 2022-04-01 06:20 214阅读 0赞

### 文章目录 ###

*   *   *   *  康拓展开
             *  逆康拓展开

#### 康拓展开 ####

> 康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。设有n个数（1，2，3，4,…,n），可以有组成不同(n!种)的排列组合，康托展开表示的就是是当前排列组合在n个不同元素的全排列中的名次。  
> 康托展开也是一个数组到一个数的映射，因此也是可用于hash，用于空间压缩。比如在保存一个序列，我们可能需要开一个数组，如果能够把它映射成一个自然数， 则只需要保存一个整数，大大压缩空间。比如八数码问题

X = a \[ 0 \] ∗ ( n − 1 ) ! + a \[ 1 \] ∗ ( n − 2 ) ! + . . . + a \[ n − 1 \] ∗ 0 ! X=a\[0\]\*(n-1)!+a\[1\]\*(n-2)!+...+a\[n-1\]\*0! X=a\[0\]∗(n−1)!\+a\[1\]∗(n−2)!\+...\+a\[n−1\]∗0!  
a\[i\] 指的是位于位置i后面的数小于a\[i\]值的个数,后面乘的就是后面还有多少个数的阶乘  
0 <= a\[i\] <= i, 0 <= i < n  
*说明* ：这个算出来的数康拖展开值，是在(所有排列次序 - 1)的值  
**举例：**  
在（1，2，3，4，5）5个数的排列组合中，计算 34152的康托展开值。

根据公式：

X = 2 * 4! + 2 * 3! + 0 * 2! + 1 * 1! + 0 * 0! 
    = 2 * 24 + 2 * 6 + 1 
    = 61

所以比 34152 小的组合有61个，即34152是排第62

**代码实现：**

//返回数组a中当下顺序的康托映射
    int cantor(int a[], int n)       //n为数组的长度
    { 
    	int ans = 0;
    	for(int i = 0; i < n; i++)
    	{ 
    		int x = 0;               //x用于记录公式前面的a[i]
    		int c = 1, m = 1;        //m记录后面的阶乘，c用于记录循环次数(这个数后面有几个数)
    		for(int j = i + 1; j < n; j++)
    		{ 
    			if(a[j] < a[i]) 
    				x++;
    			m *= c; 
    			c++;
    		}
    		ans += x * m;
    	}
    	return ans;
    }

--------------------

#### 逆康拓展开 ####

> 康托展开是从序列到自然数的映射且是可逆的，逆康托展开便是从自然数到序列的映射

**举例：**  
在（1，2，3，4，5) 给出康托展开值为61，算出其排列组合  
具体过程如下：  
用 61 / 4! = 2余13，说明 ,说明比首位小的数有2个，所以首位为3。  
用 13 / 3! = 2余1，说明 ，说明在第二位之后小于第二位的数有2个，所以第二位为4。  
用 1 / 2! = 0余1，说明 ，说明在第三位之后没有小于第三位的数，所以第三位为1。  
用 1 / 1! = 1余0，说明 ，说明在第二位之后小于第四位的数有1个，所以第四位为5。  
剩下的一位数即为2

即排列组合为34152

**代码实现：**

static const int FAC[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};   // 阶乘
        
        //康托展开逆运算
        void decantor(int x, int n)
        { 
            vector<int> v;  // 存放当前可选数
            vector<int> a;  // 所求排列组合
            for(int i=1;i<=n;i++)
                v.push_back(i);
            for(int i=m;i>=1;i--)
            { 
                int r = x % FAC[i-1];
                int t = x / FAC[i-1];
                x = r;
                sort(v.begin(),v.end());// 从小到大排序 
                a.push_back(v[t]);      // 剩余数里第t+1个数为当前位
                v.erase(v.begin()+t);   // 移除选做当前位的数
            }
        }