如何通过过滤子集大小与数量加速集合划分生成？

现有成熟方案的性能瓶颈 #

Python、Ruby社区已有集合划分的成熟实现方案，但当待划分元素数量N达到12或13时，生成速度会显著变慢。

业务场景背景 #

我需要通过集合划分将图片集适配到竖版或横版纸张，以尽可能减少留白。此前尝试过二维装箱算法，但生成的方案效果不佳，其他装箱方案又过于复杂。目前确定的可行方案为：

• 将图片分组，每组缩放至相同高度，每行放置一组图片
• 组合多行形成竖版或横版布局（示意图：图片布局示意图）
• 同时过滤两类候选方案：
  • 图片缩放幅度过大的（需保证每张图片分配的面积相近）
  • 留白过多的

该方案在处理10-11张图片时表现良好，但处理12张及以上图片时速度过慢。使用more-itertools库的set_partitions()方法也存在同样的性能问题——生成的大量集合划分中包含大量无效情况：单元素子集、子集数量过少的划分，而我的场景不需要单元素子集，且需满足子集数量的最小值（该值根据横竖版布局调整，并非N的平方根）。

核心优化需求 #

能否优化集合划分的生成逻辑，直接跳过以下几类无效划分：

必须跳过的划分类型 #

• 包含尺寸小于X的子集的集合划分
• 子集数量少于Y的集合划分

可选跳过的划分类型 #

• 包含尺寸大于X的子集的集合划分
• 子集数量多于Y的集合划分
  其中X、Y可根据不同的元素数量N灵活调整。

补充可行方案 #

我还找到一个生成指定k个子集划分的实现方案，速度表现尚可。

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