CODEWITHSUNDEEP
pythonloops
Pigna
Pigna

Reputation: 2924

Where's the error in this for loop to generate a list of ordered non-repeated combinations?

Given an integer variable n, say 3, I want to obtain these combinations: [1, 2, 3, 12, 13, 23, 123] and save them in a list. This is what I wrote:

cmb = []
for i in xrange(1,n+1):
    for j in xrange(i,n+1):
        cmb.extend(list(itertools.combinations(xrange(i,n+1),j)))

But when I print I get some unwanted and repeated tuples:

n = 3 : [(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3), (2, 3)]

n = 4 : [(1,), (2,), (3,), (4,), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4), (2, 3), (2, 4), (3, 4), (2, 3, 4)]

n = 5 : ...

What am I doing wrong?

Upvotes: 4

Views: 61

Answers (2)

Shashank
Shashank

Reputation: 13869

JuniorCompressor has already answered your question, but here is a list comprehension solution with bitmask to filter elements from the original set so that unique elements of the powerset can be generated:

>>> sorted([tuple(x for i, x in enumerate([1, 2, 3]) if y & 2**i) 
...         for y in range(1, 8)], key=len)
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Upvotes: 1

JuniorCompressor
JuniorCompressor

Reputation: 20025

The problem with your code is that you changed continuously your input range. For example you took 2 elements from [1, 2, 3], but also 2 elements from [2, 3]. You should take your combinations from the same range and just change the number of elements you get at each time. For this purpose, you don't need a double loop:

import itertools
cmb = []
for i in xrange(1, n + 1):
    cmb.extend(itertools.combinations(xrange(1, n + 1), i))

You can also implement the same thing as:

from itertools import chain, combinations
n = 3
print list(chain.from_iterable(
    combinations(xrange(1, n + 1), i) for i in xrange(1, n + 1)
))

Output:

[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Upvotes: 2

Related Questions