如何确定一个集合的所有排列，具有重复的符号，但*没有* "functionally identical" 个集合
How to determine all permutations of a set, with repeated symbols, but *without* "functionally identical" sets
假设以下符号集：[A, B, C]
假设以下结果集大小为 4。
我想生成所有排列的列表，其中包含重复的符号，但没有 "functionally identical" 项。
即：[A, A, A, A] 是 "functionally identical" 到 [B, B, B, B]，因此 [B, B, B, B] 不应该 在最终结果等
我尝试生成完整的 3^4 种可能性，然后 "rotating the symbols"，一个一个地检查是否存在欺骗并删除它们，但我意识到这没有捕捉到 "two symbols swap" 的情况，当然，当增加符号数量和集合大小时，还有很多其他 "symbol swap" 情况我没有考虑。另外，"generate the worst case and then prune" 似乎是一个糟糕的算法，我相信有更好的方法。
这是预期输出的手动生成结果：
['A', 'A', 'A', 'A']
['A', 'A', 'A', 'B']
['A', 'A', 'B', 'A']
['A', 'A', 'B', 'B']
['A', 'A', 'B', 'C']
['A', 'B', 'A', 'A']
['A', 'B', 'A', 'B']
['A', 'B', 'A', 'C']
['A', 'B', 'B', 'A']
['A', 'B', 'B', 'B']
['A', 'B', 'B', 'C']
['A', 'B', 'C', 'A']
['A', 'B', 'C', 'B']
['A', 'B', 'C', 'C']
（当然，在某些时候我想扩展符号集大小和结果集大小以查看我得到的结果。）
（首选语言是 python 但我不挑剔，我只是想了解算法）
编辑：让我澄清一下我对 "functionally identical" 的定义。本质上，重要的是结果的 "topology"。例如，假设在生成集合后将随机颜色分配给符号。
[A A A A] 仅表示 "All the items are the same color"，因此，[B B B B] 在功能上是相同的。两者之间没有区别，因为我们不知道要为A或B分配什么随机颜色，我们只知道它们都是相同的颜色。
另一个例子：
[A A A B] 在功能上与 [B B B C] 相同，因为同样，我们不知道什么颜色将分配给什么符号，我们只知道 "The last color is different from the first three."
顺序很重要！
[A A A B] != [B A A A]。在第一个示例中，除 LAST 项目外，所有项目都是相同的颜色。在第二个示例中，除第一个项目外，所有项目都是相同的颜色。
这绝对是一个数学构造，比简单的排列更高级，我只是不知道它的名字。
这是执行此操作的递归算法。关键思想是为了打破不同字母之间的对称性，我们只允许添加一个已经使用过的字母，或者 第一个 个未使用的字母。
给定部分解决方案t：
- 如果
t有要求的长度，yield它。
- 否则：
- 对于
t 中已有的每个不同的字母，通过用后者扩展 t 来递归。
- 如果
t 没有使用每个可能的字母，则通过使用第一个未使用的字母扩展 t 来递归。
这是一个 Python 实现，作为递归生成器函数：
def gen_seqs(letters, n):
def helper(used, t):
if len(t) == n:
yield t
else:
for i in range(used):
yield from helper(used, t + letters[i])
if used < len(letters):
yield from helper(used + 1, t + letters[used])
return helper(0, '')
示例：
>>> for t in gen_seqs('ABC', 4):
... print(t)
...
AAAA
AAAB
AABA
AABB
AABC
ABAA
ABAB
ABAC
ABBA
ABBB
ABBC
ABCA
ABCB
ABCC
假设以下符号集：[A, B, C]
假设以下结果集大小为 4。
我想生成所有排列的列表，其中包含重复的符号，但没有 "functionally identical" 项。
即：[A, A, A, A] 是 "functionally identical" 到 [B, B, B, B]，因此 [B, B, B, B] 不应该 在最终结果等
我尝试生成完整的 3^4 种可能性，然后 "rotating the symbols"，一个一个地检查是否存在欺骗并删除它们，但我意识到这没有捕捉到 "two symbols swap" 的情况，当然，当增加符号数量和集合大小时，还有很多其他 "symbol swap" 情况我没有考虑。另外，"generate the worst case and then prune" 似乎是一个糟糕的算法，我相信有更好的方法。
这是预期输出的手动生成结果：
['A', 'A', 'A', 'A']
['A', 'A', 'A', 'B']
['A', 'A', 'B', 'A']
['A', 'A', 'B', 'B']
['A', 'A', 'B', 'C']
['A', 'B', 'A', 'A']
['A', 'B', 'A', 'B']
['A', 'B', 'A', 'C']
['A', 'B', 'B', 'A']
['A', 'B', 'B', 'B']
['A', 'B', 'B', 'C']
['A', 'B', 'C', 'A']
['A', 'B', 'C', 'B']
['A', 'B', 'C', 'C']
（当然，在某些时候我想扩展符号集大小和结果集大小以查看我得到的结果。）
（首选语言是 python 但我不挑剔，我只是想了解算法）
编辑：让我澄清一下我对 "functionally identical" 的定义。本质上，重要的是结果的 "topology"。例如，假设在生成集合后将随机颜色分配给符号。
[A A A A] 仅表示 "All the items are the same color"，因此，[B B B B] 在功能上是相同的。两者之间没有区别，因为我们不知道要为A或B分配什么随机颜色，我们只知道它们都是相同的颜色。
另一个例子： [A A A B] 在功能上与 [B B B C] 相同，因为同样，我们不知道什么颜色将分配给什么符号，我们只知道 "The last color is different from the first three."
顺序很重要！ [A A A B] != [B A A A]。在第一个示例中，除 LAST 项目外，所有项目都是相同的颜色。在第二个示例中，除第一个项目外，所有项目都是相同的颜色。
这绝对是一个数学构造，比简单的排列更高级，我只是不知道它的名字。
这是执行此操作的递归算法。关键思想是为了打破不同字母之间的对称性，我们只允许添加一个已经使用过的字母，或者 第一个 个未使用的字母。
给定部分解决方案t：
- 如果
t有要求的长度，yield它。 - 否则：
- 对于
t中已有的每个不同的字母，通过用后者扩展t来递归。 - 如果
t没有使用每个可能的字母，则通过使用第一个未使用的字母扩展t来递归。
- 对于
这是一个 Python 实现，作为递归生成器函数：
def gen_seqs(letters, n):
def helper(used, t):
if len(t) == n:
yield t
else:
for i in range(used):
yield from helper(used, t + letters[i])
if used < len(letters):
yield from helper(used + 1, t + letters[used])
return helper(0, '')
示例：
>>> for t in gen_seqs('ABC', 4):
... print(t)
...
AAAA
AAAB
AABA
AABB
AABC
ABAA
ABAB
ABAC
ABBA
ABBB
ABBC
ABCA
ABCB
ABCC