# 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