我想编写一个算法来生成所有可能的独特排列，n组m人可以坐在有mn个座位的圆形餐桌周围。就餐者的安排仅考虑团体成员身份，而不识别团体内的个人。任何两个排列在反射或旋转下都被认为是相同的。
例如，这是n=3且m=4的排列。我已将其显示为正方形，但几何形状无关紧要。
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
我首先采用的策略是迭代深度优先搜索。我将候选者存储在堆栈中，其中每个候选者都是一个整数数组。在每次迭代中，我都会向每个候选数组添加符合规则的整数。如果达到所需的数组长度，则我将完成的排列从堆栈中弹出并将其存储在列表中。否则我会将其添加回堆栈以供进一步考虑。
上面生成了很多重复项。例如，这些都是等价的：
然后，我从上述过程生成的数组列表中删除重复项。为此，我比较数组以考虑旋转（通过使用增加的偏移量进行成对比较）和反射。这很耗时。
我的问题是这样的：如何通过在生成过程中避免重复来加速上述过程？一个部分答案是从修复数组中的第一个元素开始，即坚持以零开头，因为任何排列可以旋转以使该组在特定位置用零表示。这是一个改进，因为在上述情况下它只会生成 6 个排列，而不是整个 24 个。但是，我可以做得更好吗？
您可以将每个排列映射到该排列的所有重复项的规范代表，而不是比较所有排列对来检查该对中是否存在重复项。
如果排列的长度为
m*nNm*nNN*N * m*nN * m*n在这里，我使用 more_itertools.distinct_permutations 生成所有座位，然后使用将每个座位映射到其规范代表的函数过滤掉重复项，然后使用 python
setdef canonical(seq):
qes = seq[::-1]
return min(
min(seq[i:]+seq[:i] for i in range(len(seq))),
min(qes[i:]+qes[:i] for i in range(len(seq)))
)
from more_itertools import distinct_permutations
from string import printable as alphabet
def seatings(n, m):
'''all possible seatings for n groups of m people, up to reflection/rotation'''
pool = alphabet[:n] * m
return {''.join(canonical(seating)) for seating in distinct_permutations(pool)}
l42 = seatings(4, 2)
print(len(l42))
# 171
print(l42)
# {'01102332', '00122331', '01230123', '01012323', '00121233', '01220313', '01303212', '00112323', '01133202', '01132302', '01122303', '01231023', '00213132', '01203312', '01302231', '00211233', '01212033', '01331022', '01230213', '00123321', '00131322', '01122033', '00212313', '02023113', '01230132', '02121303', '01230231', '02211303', '01012233', '02130213', '01032123', '01312023', '00112233', '01321203', '01012332', '01123023', '00321123', '00123213', '01203213', '02021133', '01202331', '00122133', '01120323', '01130232', '02120313', '01203132', '00312123', '01223031', '00122313', '01323102', '01232031', '01232013', '01312302', '02113032', '00213312', '00132123', '01320312', '01130223', '01202313', '02113203', '01133022', '01021233', '01223103', '01022133', '02112303', '00213213', '01233102', '00113223', '00123231', '01230312', '00312213', '01302123', '00231213', '01310232', '01213302', '01231203', '00131223', '00221313', '00133122', '02130312', '01302213', '02203113', '00212133', '01213032', '00113322', '01320231', '01302312', '01331202', '02031213', '00132312', '01312032', '01303122', '01221303', '01221033', '01123203', '01223013', '01231032', '01031223', '02113023', '00211323', '00223113', '00132213', '00121332', '01021323', '01220133', '01301322', '00123132', '00132132', '00311223', '00221133', '00133212', '00113232', '01230321', '01120233', '01132032', '00213123', '01321302', '01212303', '00232113', '01022313', '01120332', '01220331', '00123312', '01102323', '01103223', '01313022', '01203231', '00112332', '00132231', '01102233', '01213203', '01231302', '01201323', '01320213', '00211332', '02021313', '01312203', '02131203', '01203123', '01013223', '01132023', '00131232', '01130322', '01013232', '01313202', '01330212', '02112033', '01023132', '01210323', '01232103', '00231123', '01123302', '01213023', '01320132', '01123032', '00123123', '00121323', '01201233', '01013322', '01201332', '01023213', '00231132', '01021332', '01023123', '01310223', '01132203', '01203321', '01210233', '02031123', '01302132', '01202133'}
l43 = seatings(4, 3)
print(len(l43))
# 15402
print(l43)
# {'010113233202', '011320210332', '012013210323', '012303013212', '002102133123', '001021332213', '011312023023', '013103022123', '011320302231', '001212031233', ..., '002132213013', '013212020313', '010133212023'}
郑重声明，
distinct_permutations('000111222333')