Mivik 展开(大雾

Mivik 展开(大雾

引子

在介绍 Mivik 展开之前,我们先来看看康托展开。

在一些编程问题中,我们往往需要把一个 $1\sim n$ 的排列转化为一个正整数以便存储状态进行动态规划。比较平凡的思路是把原排列当作一个 $n$ 进制数然后直接计算,但是这样额外的开销过大,因为我们知道 $1\sim n$ 的排列一共只有 $n!$ 种,但我们这样计算出来的最大状态是 $n^n$ 级别的。因此我们使用康托展开建立起一个 $1\sim n$ 的排列到 $[1,n!]$ 中的整数的一个双射,这里选其中排列到整数的这一部分讲解。

康托展开计算的整数就是这个排列在所有排列按字典序排序后的排名,也就是 $1\sim n$ 的排列中比这个排列字典序小的排列个数。我们逐位考虑这个排列 $a$。已知排列的第 1 位是 $a_1$ ,那么根据字典序的定义,我们就知道第 1 位小于 $a_1$ 的排列字典序都是比这个排列小的,于是我们给排名加上 $a_1(n-1)!$;此后我们看第二位,然后我们发现第 2 位比 $a_2$ 小 且不等于 $a_1$ 的排列的字典序也都是小于它的,再加上排名… 以此类推,我们得到康托展开的公式:
$$
index=\sum_{i=1}^n c_i(n-i)!
$$
其中 $c_i$ 代表 ${a_1,a_2,\cdots,a_i}$ 的补集中共有多少个数小于 $a_i$。

然后进入正题!

定义

  • 多重集(Multiset):元素可以出现多次的集合。

  • 多重集的宇宙(Universe):多重集的元素值域,即多重集中每个元素都属于该多重集的宇宙。

  • 多重集的上界:一个正整数。本文中多重集的宇宙均为 $[1,上界]$。

  • $A$:一个多重集。

  • $a$:$A$ 中的所有元素升序排序后得到的一个序列。

  • $a_i$:$a$ 的第 $i$ 项元素,下标从 1 开始。

问题

已知大小为 $n$ ,上界为 $m$ 的多重集共有 $\binom{m+n-1}{n}$ 种(可用隔板法证明),要求建立一个指定范围内的多重集到 $[1,\binom{m+n-1}{n}]$ 内正整数的双射。

思路

咕咕咕

代码

在此!

作者

Mivik

发布于

2020-10-04

更新于

2021-05-31

许可协议

评论