如何求解分拆的共轭？是否存在无需绘制Ferrers-Young图的算法？

当然有不用依赖Ferrers-Young图的分拆共轭计算方法！本质上，分拆的共轭就是把原分拆的行长度统计转换成列长度统计——原分拆里的每个数代表一行的格子数，共轭分拆的每个数则代表一列的格子数。下面给你两种直观且易实现的算法：

方法一：计数统计法 #

这个方法的核心是统计原分拆中大于等于某个数的元素个数，具体步骤如下：

• 先找出原分拆中的最大值（也就是Ferrers图的行数，同时也是共轭分拆的第一个元素）。
• 从1到这个最大值依次遍历每个整数k，统计原分拆里大于等于k的元素数量，这个数量就是共轭分拆中的第k个元素。
• 把所有统计得到的数按顺序排列，就是原分拆的共轭。

举个例子，原分拆是7=4+2+1：

• 最大值是4，所以我们遍历1到4：
  • k=1：原分拆里≥1的元素有3个（4、2、1）→ 共轭的第一个数是3
  • k=2：原分拆里≥2的元素有2个（4、2）→ 共轭的第二个数是2
  • k=3：原分拆里≥3的元素有1个（4）→ 共轭的第三个数是1
  • k=4：原分拆里≥4的元素有1个（4）→ 共轭的第四个数是1
• 最终得到共轭分拆3+2+1+1，和画图的结果一致。

方法二：数组映射法 #

如果用数组来存储原分拆，这个方法更适合编程实现：

• 假设原分拆用数组parts表示，比如[4,2,1]。
• 创建一个长度为max(parts)+1的计数数组count，初始值全为0。
• 遍历原分拆的每个元素p，把count[1]到count[p]的每个值都加1（这相当于给每一列的格子数计数）。
• 最后从count[1]开始，把所有非零的数按顺序收集起来，就是共轭分拆。

还是用[4,2,1]举例：

• 初始化count = [0,0,0,0,0]（因为max是4，长度设为5）
• 处理4：count[1]到count[4]各加1 → count变成[0,1,1,1,1]
• 处理2：count[1]到count[2]各加1 → count变成[0,2,2,1,1]
• 处理1：count[1]加1 → count变成[0,3,2,1,1]
• 收集count[1]到count[4]的非零值：3,2,1,1，就是共轭分拆。

补充说明 #

这两种方法都完全不需要绘制图形，核心都是把原分拆的“行”维度信息转换为“列”维度的统计结果，不管是手动计算还是写代码实现都很方便。

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