离散数学

组合字典序覆盖

定义

  1. 字典序定义偏序关系
  2. 串必须递增排列 e.g. $132$ 不合法
  3. 定义字符集 $\sum$ 的 k-组合串的长度为 $k$

求解

  1. 写出最大组合
  2. 倒序查找第一个不与最大组合相同的位
  3. 该位用覆盖代替
  4. 对应后缀用最小组合代替
例子

已知字符集 $\sum = {1,2,3,4,5,6,7,8}$ 求 5-组合 $13458$ 的覆盖

  1. 写出最大组合 $45678$
  2. 第一个不与最大组合相同的位为 $5 \neq 7$
  3. 用覆盖代替该位 $\Rightarrow$ $1346_$
  4. 后缀用最小组合代替 $\Rightarrow$ $13467$