How Can I Efficiently Generate Unique Permutations of a Multiset?

Counting Unique Permutations

Itertools' permutations function treats elements as unique by their position, not value. As a result, duplicates can emerge, such as in the example provided: [(1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1)].

Avoiding Duplicates

The original request was for an algorithm that avoids these duplicates without resorting to post-filtering due to the large number of permutations involved.

Multiset Permutations in sympy

For such cases, sympy offers the multiset_permutations iterator. Unlike permutations, this iterator treats elements as unique based on their values, not their positions.

Consider the following examples:

>>> from sympy.utilities.iterables import multiset_permutations
>>> list(multiset_permutations([1,1,1]))
[[1, 1, 1]]
>>> list(multiset_permutations([1,1,2]))
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

As you can see, multiset_permutations produces only unique permutations.

The above is the detailed content of How Can I Efficiently Generate Unique Permutations of a Multiset?. For more information, please follow other related articles on the PHP Chinese website!