Permutation, Combination and Frozenset

It is inspired by SFO question on how to filter duplicated tuples from results of itertools.permutations(). The original question is here:

I have N positions, and each position can be either 0 or 1. I have fixed number of 1s, and I want to permutate these fixed number of 1s in these N positions.

from itertools import permutations
p =[0for k in xrange(6)]
    for k in xrange(0,3):        
p[k]=1print(list(permutations(p)))

But above result contains four [0,0,0,1,1,1] in the list. I only want one of them. How can I get rid of these duplicates?

Above code is not working because here for a series of unique combinations, permutations() call will generate more than expected. To permutations(), the tuple (0,1) is not duplicated to (1,0).

itertools.combination() will return all possible tuples regardless to the order. Which means tuple (0,1) and (1,0), either will show up in the results.

Notes: hash((0,1)) != hash((1,0)) but it is not always true for default hash values on tuple. Below is a concidence:

hash((1, -1, 0))
Out[143]: -2528505496374624146

hash((1, 0, -1))
Out[144]: -2528505496374624146

However, it is not smoothy to turn a result from permutations() to generate the same result as combinations() shows. Below is a solution. I firstly picked up set but the problem is that set cannot be hashed because it is an mutable type. For example, list is a mutable type which can add or pop. So list, by default, has no hash support.

To mitigate it, frozenset is a choice. It is an immutable type which won't change the values.

Finally the way to convert permutations() to combinations() is as below:

[tuple(x) for x in set([frozenset(x) for x in itertools.permutations(ls, 2)])]
Out[126]: [(1, 2), (0, 2), (0, 1)]

list(itertools.combinations(ls, 2))
Out[127]: [(0, 1), (0, 2), (1, 2)]

Here we have couple of concepts to clarify:

itertools.permutation(l, r) generates all r depth permutations based on list l.

By the way, there are still more toys from itertools package. product will generate Cartesian products for sets. Repeat is the depth or exponential part. Here product is the concept of cross-product, or, outer product. Below sample generates an iterator to cover a 3 by 3 square for basic medium filter.

In [80]: from itertools import product

In [81]: a = [0,1, 2]

In [82]: list(product(a, repeat=2))
Out[82]: [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]

References

Stackoverflow original thread, http://stackoverflow.com/questions/43816965/permutation-without-duplicates-in-python#43817007