Why do python's itertools permutations have a lot of repeated elements?

Question

I am trying to find the different permutations of the string "0000111". All the different strings that contain three 1s and four 0s. This is my code:

p = itertools.permutations("0000111")
l = list(p)
print len(l) #5040
print len(set(l)) #35

What's wrong? And is there a better way?

Answer 1

It's in the manual: http://docs.python.org/2.7/library/itertools.html#itertools.permutations

Elements are treated as unique based on their position, not on their value. So if the input elements are unique, there will be no repeat values in each permutation.

That means that itertools.permutations('000') will happily give you 3! = 6 results, where all are '000'.

See for yourself: http://ideone.com/gzqolT

---

Your problem could be solved, if you interpreted your problem as a bitmap. itertools.combinations(S,r) gives you all subsets of S with r items. In your example S = range(7) and r = 3.

A full working solution:

list('{0:07b}'.format(sum(subset))
     for subset in itertools.combinations((2**s for s in range(7)), 3))

A little bit of explanation:

• (2**s for s in range(7)) is a generator of all powers of 2 upto 2^6.
• itertools.combinations(…, 3) finds all subsets with 3 items of these powers of 2.
• sum(subset) calculates the sum of e.g. [1,2,4] = 7.
• '{0:07b}'.format(…) formats the input int as a binary number that is padded with zeros upto a length of 7.