列表与枚举:不重复也不遗漏
约 10 分钟
有些问题不是一次计算就能解决,而要找出所有可能。例如用 1、2、3 组成没有重复数字的两位数,或者从三种上衣和两条裤子中搭配。随意想到哪写到哪,容易重复和漏掉;有顺序地枚举才可靠。
固定一个,再变化另一个
组成两位数时先固定十位为 1,个位可选 2、3,得到 12、13;再固定十位为 2,得到 21、23;最后固定 3。这个方法把大问题分成结构相同的小组。
用表格保存状态
搭配衣服可以让行表示上衣、列表示裤子,每个格子是一种搭配。表格不仅帮助计数,还能说明为什么没有遗漏。若某种组合不允许,就在对应格中划掉,而不是忘记它曾被考虑。
先定规则再数
“从 A 到 B 可以走哪几条路”要先说明能否走回头路、能否重复经过同一点。规则不同,答案完全不同。枚举之前把限制写在表头,能防止做到一半偷偷改变规则。
检查重复
选两个人组队时,“甲乙”和“乙甲”是否同一种,要看顺序有没有意义;安排冠亚军时顺序有意义,则是两种结果。对象相同不代表方案相同,必须回到问题语境。
找到结构后再概括
枚举少量例子可以发现规律,但不能只凭前三个就宣布永远如此。先列全小规模情况,解释变化规则,再尝试推广。
练一练:早餐有 3 种主食、2 种饮料,其中牛奶不能配某一种主食。画表列出全部可选套餐并说明如何确认不重不漏。
小纸条
怎样枚举才能尽量做到不重复、不遗漏?