环形餐桌分组座位唯一排列生成算法去重优化问询

我需要写一个算法，生成n组、每组m人的环形餐桌就座的所有唯一排列，规则如下：

• 只考虑人员所属组别，不区分组内个体；
• 旋转或翻转后相同的排列视为同一种情况；
• 补充约束：相邻就座的人员不能来自同一组。

举个例子，当n=4、m=3时，一种排列如下（用方形展示，几何形态不影响）：

0 1 2 0
1     3
2     1
3 2 3 0

以下这些排列都和上面的视为相同：

1 2 0 3        0 2 1 0        2 3 2 3
0     1        3     1        1     0 
1     0        1     2        0     1 
2 3 2 3        0 3 2 3        1 2 0 3

我最开始用迭代式深度优先搜索（iterative depth-first search）：把候选排列存在栈里，每个候选是整数数组；每次迭代给候选数组加符合规则的整数，达到目标长度就弹出存到列表，否则重新入栈继续处理。但这个方法会生成大量重复排列，比如上面例子里的24个数组都是等价的，后续要通过比较旋转、翻转后的数组来去重，特别耗时。

我已经想到固定数组首个元素为0（通过旋转让0组处于固定位置），能把示例中的重复生成量从24降到6，但想知道能不能进一步优化？

可以通过在搜索阶段添加更多约束，从根源上避免生成翻转或其他等价排列，具体思路如下：

1. 固定首个元素+限制第二个元素范围，消除翻转重复 #

固定第一个元素为0后，翻转等价的排列会出现「第一个元素是0，第二个元素和原排列最后一个元素交换」的情况。为了避免生成这类重复，我们可以规定第二个元素的组别小于最后一个元素的组别（搜索到最后一个位置时做判断）；或者更高效的方式：在生成第二个元素时，只允许选择大于0的组别中特定范围的取值（比如规定第二个元素只能选1、2，不能选3），直接从搜索起点就排除掉翻转等价的分支。

比如n=4的例子里，固定第一个元素为0后，原本第二个元素可选1、2、3，现在限制只能选1或2，就能把重复量从6再减半到3。

2. 实时统计各组人数，提前剪枝无效分支 #

在搜索过程中，每添加一个组别就实时统计该组已使用的人数：

• 如果某个组的人数已经达到m，直接跳过该组的候选；
• 如果剩余座位数不足以让其他组凑够m人，直接剪枝当前分支。

这不仅能减少无效搜索，还能避免生成不符合「每组刚好m人」的排列，从源头减少后续需要处理的候选数量。

3. 对称位置约束，直接排除翻转等价排列 #

对于环形排列的第i个位置和第total_seats - 1 - i个位置（total_seats = n*m），当i < total_seats -1 -i时，规定第i个位置的组别 ≤ 第total_seats-1 -i个位置的组别。这样就能确保不会生成翻转后等价的排列——因为翻转后这两个位置会交换，而我们只保留满足这个大小关系的排列，直接排除掉翻转后的重复分支。

比如总座位数是12（n=4,m=3），位置0固定为0，位置11是最后一个位置，我们规定位置1的组别 ≤ 位置10的组别、位置2的组别 ≤ 位置9的组别……以此类推，就能完全避免生成翻转等价的排列。

4. 无差异组别顺序约束（可选） #

如果所有组别只是标签、没有实际差异，可以规定在搜索时，首次出现的组别顺序是递增的，避免生成因为组别编号互换导致的重复排列。比如第一次出现的非0组别必须是1，第一次出现的非0非1组别必须是2，以此类推，进一步减少不必要的搜索分支。

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