P27 - 互斥分组

2026-09-07 00:00    #Haskell   #99题   #组合  

P27 - 互斥分组

Group elements into disjoint subsets

官方模块：Problems.P27　核心函数：disjointGroups

← P26 生成所有 K 元组合 | P28 按子列表长度排序 →

题目描述

给定各组的指定大小（列表长度不限，元素互不相同），将元素划分成互斥的若干子组，返回所有可能的分组方案。

例如：disjointGroups [2,3,4] [1..9] 表示将 9 个元素分成大小为 2、3、4 的三个组。

disjointGroups 是什么意思

disjointGroups = 互斥分组

把一堆元素不重不漏地分到若干组里，每组大小事先给定。

签名含义

1disjointGroups :: [Int] -> [a] -> [[[a]]]
2--                各组大小   元素     所有分法

例子

1disjointGroups [2, 3] [1,2,3,4,5]

意思是：5 个人分成 2 人一组 + 3 人一组，两组互不重叠、合起来是全部 5 人。

一种可能的结果：

1[ [[1,2], [3,4,5]]
2, [[1,3], [2,4,5]]
3, ...
4]

和 combinations 的区别

combinationsdisjointGroups
做什么只选 一组 k 个按多个大小 连续选多组
剩余元素不管必须分完 / 组间不能重叠
例子从 5 人选 2 人从 5 人分成 2+3 两组

可以理解为：先 combinations n1 xs 选出第一组，再从剩下的里 combinations n2 ...，一路做完所有组大小。

名字里的 disjoint

disjoint = 互不相交：任意两个组没有公共元素。

函数签名

1disjointGroups :: Eq a => [Int] -> [a] -> [[[a]]]

返回 [[[a]]]——外层列表是各种分组方案，每个方案是一个组列表，每个组是一个元素列表。

实现

方法一：递归 choose（标准回溯）

 1import Data.List (foldl')
 2
 3disjointGroups :: [Int] -> [a] -> [[[a]]]
 4disjointGroups [] xs
 5  | null xs   = [[]]
 6  | otherwise = []
 7disjointGroups (n:ns) xs =
 8  [ group : groups
 9  | (group, rest) <- choose n xs
10  , groups <- disjointGroups ns rest
11  ]
12
13choose :: Int -> [a] -> [([a], [a])]
14choose 0 xs     = [([], xs)]
15choose _ []     = []
16choose n (x:xs)
17  | n < 0 = []
18  | otherwise =
19      [ (x : picked, rest) | (picked, rest) <- choose (n - 1) xs ]
20      ++
21      [ (picked, x : rest) | (picked, rest) <- choose n xs ]

核心递归：先为第一个组大小 N 生成所有可能组合以及剩余元素，再递归处理剩下的组。

choose n xs 返回所有 (选中的 N 个元素, 剩余的元素) 对。

方法一详解

两层结构：choose 选一组，disjointGroups 连续选多组。

1. choose n xs：从 xs 里选 n 个

1choose :: Int -> [a] -> [([a], [a])]
2-- 返回：所有 (选中的 n 个, 剩下的)

对首元素 x 只有两种选择：

1-- 选 x
2[ (x : picked, rest) | (picked, rest) <- choose (n - 1) xs ]
3
4-- 不选 x
5[ (picked, x : rest) | (picked, rest) <- choose n xs ]

边界：

情况结果含义
choose 0 xs[([], xs)]选 0 个：空组 + 全剩
choose _ [][]还要选但列表空了 → 无解
n < 0[]非法

例子：choose 2 [1,2,3]

 1选 1: choose 1 [2,3]
 2  选 2: choose 0 [3] → ([],[3]) → (1:2, [3]) = ([1,2],[3])
 3  不选 2: choose 1 [3]
 4    选 3: ([],[ ]) → ([1,3],[])
 5    不选 3: 失败
 6
 7不选 1: choose 2 [2,3]
 8  选 2: choose 1 [3] → ([2,3],[])
 9  不选 2: choose 2 [3] → 失败（只剩 1 个）
10
11结果: [([1,2],[3]), ([1,3],[2]), ([2,3],[1])]

2. disjointGroups (n:ns) xs：按大小列表连续分组

1disjointGroups (n:ns) xs =
2  [ group : groups
3  | (group, rest) <- choose n xs        -- 先选第一组（大小 n）
4  , groups <- disjointGroups ns rest    -- 用剩余元素继续分后面的组
5  ]

读法：

  1. 用 choose n xs 得到所有 (第一组, 剩余)
  2. 对每个 rest，递归 disjointGroups ns rest
  3. 拼成 第一组 : 后面各组

边界：

1disjointGroups [] xs
2  | null xs   = [[]]   -- 组大小用完，元素也用完 → 一种空方案
3  | otherwise = []     -- 组用完了还有元素 → 分不完，失败

例子：disjointGroups [2,1] [1,2,3]

1第一组大小 2，choose 2 [1,2,3] 得到：
2  ([1,2],[3]) → 再 disjointGroups [1] [3]
3                  → 选 1 个：[([3],[])] → 方案 [[1,2],[3]]
4  ([1,3],[2]) → 方案 [[1,3],[2]]
5  ([2,3],[1]) → 方案 [[2,3],[1]]

3. 整体图示

 1disjointGroups [2,3] xs
 2       │
 3       ▼
 4  choose 2 xs  ──►  (group1, rest1)
 5       │
 6       ▼
 7  disjointGroups [3] rest1
 8       │
 9       ▼
10  choose 3 rest1 ──► (group2, rest2)
11       │
12       ▼
13  disjointGroups [] rest2
14       │
15       ▼  rest2 为空才成功
16  [[group1, group2], ...]

4. 和 P26 的关系

P26 combinations这里的 choose
返回只有选中的组合选中 + 剩余 一对
用途只要「选哪些」还要继续用剩余做下一组

disjointGroups 就是：反复 choose，每次把「没被选走的」交给下一组。

方法二：基于 P26 的 combinations

 1import Data.List (delete, foldl')
 2
 3disjointGroups :: [Int] -> [a] -> [[[a]]]
 4disjointGroups [] _ = [[]]
 5disjointGroups (n:ns) xs =
 6  [ group : groups
 7  | group <- combinations n xs
 8  , let remaining = foldl' (flip delete) xs group
 9  , groups <- disjointGroups ns remaining
10  ]

用 P26 的 combinations 生成第一个组的组合，delete 逐个删除已选元素得到剩余列表，再递归。

注意：delete 只在元素类型有 Eq 约束时有效，combinations 不需要 Eq，所以此方法有额外的类型限制。

扩展：只按原顺序切成等大组

如果不要求枚举所有分组，只想按原顺序切成等大组，可以写成：

 1disjointGroups :: Int -> [a] -> [[[a]]]
 2disjointGroups n xs
 3  | length xs `mod` n == 0 = go (length xs `div` n) xs
 4  | otherwise              = []
 5  where
 6    go 0 xs  = [[]]
 7    go k xs =
 8      [ take n xs : groups
 9      | groups <- go (k - 1) (drop n xs)
10      ]

这个函数没有枚举元素的不同归属，因此不是原题解法，只作为列表分块的对照。

方法对比

方法特点类型约束
递归 choose标准回溯，无额外类型约束无
combinations + delete语义清晰，复用已有函数Eq a
简化版只用等大小分组无

测试

1>>> length (disjointGroups [2,3,4] [1..9])
21260
3>>> disjointGroups [1,1] "ab"
4[["a","b"],["b","a"]]
5>>> disjointGroups [2,2] [1,2,3]
6[]

参考