如何筛选满足约束的排列并优化大样本场景下的执行性能？

初始小规模场景需求 #

给定数据集：

dbset = [[{'id': '10556', 'nation': 'France', 'worth': '70'}], [{'id': '14808', 'nation': 'France', 'worth': '65'}], [{'id': '11446', 'nation': 'Ghana', 'worth': '69'}], [{'id': '11419', 'nation': 'France', 'worth': '69'}], [{'id': '11185', 'nation': 'Ghana', 'worth': '69'}], [{'id': '1527', 'nation': 'Ghana', 'worth': '64'}], [{'id': '12714', 'nation': 'Moldova', 'worth': '67'}], [{'id': '2855', 'nation': 'Moldova', 'worth': '63'}], [{'id': '9620', 'nation': 'Moldova', 'worth': '71'}]]

已知可通过以下代码生成长度为4的全排列：

from itertools import permutations
perms = permutations(dbset,4)

需筛选满足以下条件的排列：

• 单个国家出现次数最多为2次
• 排列中所有元素的worth总和超过300

大规模数据场景的性能瓶颈与优化需求 #

针对小规模样本已实现上述逻辑，但当前样本量超过16000条，需生成长度为11的排列，筛选条件更新为：

• 排列的平均worth等于80（即总worth为880）
• 单个国家出现次数≤5
  目前程序已运行超1小时，寻求性能优化方案。

性能优化方案 #

1. 替换全排列为组合优先逻辑
   全排列的时间复杂度为O(n^k)（n为样本量，k为排列长度），16000选11的全排列数量是天文数字，完全无法遍历。先以组合（不考虑顺序）为目标筛选符合条件的集合，若业务确实需要排列，再从合格组合生成对应的全排列。

2. 预处理数据减少重复计算

• 按国家分组，将每组内元素的worth转为整数并排序（比如降序），方便后续快速挑选高值元素，同时避免重复的类型转换操作。
• 提前过滤掉worth偏离80过多的元素，比如只保留75-85区间内的元素（可根据实际数据分布调整），直接缩小样本池规模。

3. 剪枝策略（核心优化）
   在组合构建过程中，提前终止不可能满足条件的分支：

• 若当前累计worth加上剩余位置能取到的最大worth总和仍小于880，直接终止该分支。
• 若某国家已选数量达到5，不再从该组选取元素。
• 若剩余待选位置数 + 当前某国家已选数量 >5，直接剪枝（后续再选必然超出限制）。

4. 利用高效计算工具

• 使用itertools.combinations替代permutations先处理组合逻辑，减少不必要的顺序遍历。
• 用numpy或pandas进行批量数值计算，比如将所有worth转为numpy数组，快速筛选符合数值范围的元素，比纯Python循环效率提升数倍。

5. 并行计算加速
   若剪枝后仍有大量候选组合，可利用多进程/多线程并行处理筛选任务，充分利用CPU多核资源。例如使用multiprocessing.Pool分发筛选任务。

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