字母多重集可同时构造最大唯一集合的算法求解

核心构造规则 #

• 输入为一袋包含若干字母实例的多重集，求解目标有两个：一是计算可同时构造的唯一集合最大数量，二是输出集合数取最大值时对应的集合列表
• 构造时必须遵守以下约束：
  • 袋中每个字母实例只能使用一次，某个集合用到的字母实例，后续构造其他集合时不可复用
  • 单个集合内不能出现重复元素
  • 集合的唯一性和字符顺序无关，只要两个集合的字符组成完全一致，就视为同一个集合，不能重复计数

两类研究场景 #

• 场景1：袋中每种字母仅含1个实例

  已有明确结论：最多可构造n个唯一集合（每个集合只包含1个字母），n为袋中不同字母的种类总数

• 场景2：袋中每种字母的实例数量完全相同，均为常数k>1

  待求解内容：该场景下的通用求解思路，以及可以输出最大化集合列表的可执行算法

场景2参考示例 #

• 输入多重集：{a, a, a, a, b, b, b, b}（共2种字母，每种字母各4个实例）
• 最优构造结果：[{a}, {b}, {ab}]
• 结果说明：
  • {a,a}、{b,b}这类集合因为内部存在重复元素，属于无效集合，不能计入结果
  • 后续如果再构造{a,b}，会和已有的{ab}重复，无法新增计数
  • 构造完成后剩余未使用的字母实例为[a,a,b,b]

实际应用背景 #

该问题来自热门游戏《Minecraft》的*encoder（编码器）*装置设计需求：

• 编码器的作用是把物品编码为唯一的redstone（红石）代码，供编码存储系统使用，工作原理等价于对多个容器执行contains(item)判断，根据物品存放的容器组合生成不同代码
• 游戏中容量最大的容器double chest（双箱）只有54个槽位，最多存放54种物品。为了设计占用箱子数量更少的小型编码器，需要合理映射代码，在有限体积下充分利用所有库存空间
• 编码器设计逻辑和上述场景2完全等价：
  • 把每个箱子看作一个字符，每个代码看作一个集合
  • 每个箱子有54个槽位，对应模型里每种字符有54个重复实例的字母多重集
  • 给定n个箱子时，袋内总字母实例数为n * 54，求解目标就是给定箱子数n时，最多能构造出多少个唯一代码（集合）

内容的提问来源于stack exchange，提问作者Andrew