SymPy multiset_permutations与itertools permutations时间复杂度问询

SymPy multiset_permutations 的时间复杂度 #

sympy.utilities.iterables.multiset_permutations 专门生成含重复元素集合的唯一排列，其时间复杂度由最终输出的排列总数决定：

• 假设输入集合总元素数为 n，各重复元素的出现次数分别为 k₁, k₂, ..., kₘ，则唯一排列总数为 n! / (k₁! * k₂! * ... * kₘ!)
• 该函数通过回溯算法直接生成唯一排列，不会先生成冗余重复排列再去重，因此时间复杂度为 O(N)，其中 N 即上述的唯一排列总数。

itertools permutations 的时间复杂度 #

itertools.permutations 生成的是所有可能排列（包括因重复元素导致的重复结果）：

• 对于长度为 n 的输入，它会生成 n! 个排列，时间复杂度为 O(n!)
• 如果需要得到和 multiset_permutations 一致的唯一排列，需额外对结果去重（比如转成集合），这会进一步增加时间成本——要先处理 n! 个元素再筛选出 N 个唯一值。

实例对比（以你的示例为例） #

输入字符串 'aab'：

• 总元素数 n=3，a 出现2次，b 出现1次，唯一排列总数 N=3!/(2!*1!)=3
• multiset_permutations 直接生成3个结果，耗时对应 O(3)
• itertools.permutations 会生成6个含重复的结果，耗时对应 O(6)，若去重则需额外处理这6个元素，总耗时远高于前者。

你的示例代码 #

from sympy.utilities.iterables import multiset_permutations
from sympy import factorial
[''.join(i) for i in multiset_permutations('aab')]

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