Generate partial subsets in Python

Question

Confession: this is for a class.

I am trying to generate all subsets of length 1 - length(full set), but they must be in order.

So, with an input of (4,2), valid results would be (4), (4,2), and (2). Would not be (4,4) (2,2) or (2,4)

eta (4,2,2) should return (2,2) as well.

Length is not pre-determined.

What I have right now:

def gen_all_partials(outcomes, length):
    """
    Iterative function that enumerates the set of all sequences of
    outcomes of lengths up to given length.
    """

    answer_set = set([()])
    for dummy_idx in range(length):
        temp_set = set()
        for partial_sequence in answer_set:
            for item in outcomes:
                new_sequence = list(partial_sequence)
                new_sequence.append(item)
                temp_set.add(tuple(new_sequence))
        answer_set = temp_set
    return answer_set

This is partially obtained by a given function. I don't understand how Python is iterating over an empty set in that 2nd "for" loop. This current code outputs (4,4), (2,2), and (2,4) in addition to the "right" answers.

I'm getting hung up on the nested loops and keeping track of multiple counters and having different lengths for the desired output.

I have also tried this:

def gen_all_partials(outcomes, length):
    """
    Iterative function that enumerates the set of all sequences of
    outcomes of lengths up to given length.
    """

    answer_set = set([()])
    for dummy_idx in range(length):
        temp_set = set()
        for partial_sequence in answer_set:
            for item in outcomes:
                new_sequence = list(partial_sequence)
                new_sequence.append(item)
                if new_sequence not in temp_set:
                    temp_outcomes = list(outcomes[:])
                    add_to_set = True
                    for val in new_sequence:
                        if val in temp_outcomes:
                            order_list = []
                            for dummy_bit in val:
                                order_list.append(val.index(dummy_bit)) 
                                if order_list == order_list.sort():
                                    temp_outcomes.remove(val)
                                else:
                                    add_to_set = False
                        else: 
                            add_to_set = False
                    if add_to_set:
                        temp_set.add(tuple(new_sequence))
        answer_set = temp_set
    return answer_set

If you are allowed to use the standard library, this would be only a few lines with the use of itertools. If not, I strongly suggest that you write some wrapper functions instead of nesting that deep. It becomes confusing. — timgeb
– timgeb, Commented Jul 7, 2014 at 19:32
Your definition of "in order" seems different to mine - what should happen for e.g. (1, 2, 3)? — jonrsharpe
– jonrsharpe, Commented Jul 7, 2014 at 19:43
(1,2,3) should return (1,2), (1,3), (2,3), (1), (2), (3), and (1,2,3) but not (2,3,1) or (2,1). — mauve
– mauve, Commented Jul 7, 2014 at 19:54
Oh, I see - the elements in the subset must be in the right order. That's standard; I thought you were being required to provide the subsets in some specific order. — jonrsharpe
– jonrsharpe, Commented Jul 7, 2014 at 22:31

jonrsharpe · Accepted Answer · 2014-07-09 10:53:29Z

3

From the ever-helpful itertools recipes:

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

This includes the empty set, but you can trivially alter the range to handle that.

edited Jul 9, 2014 at 10:53

answered Jul 7, 2014 at 19:33

jonrsharpe

123k31 gold badges278 silver badges488 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

timgeb Over a year ago

I believe in this case itertools is against the spirit of the exercise :)

jonrsharpe Over a year ago

@timgeb I'm a firm believer in standing on the giants' shoulders!

mauve Over a year ago

This is super helpful for reality-land, but unfortunately, will not work for this assignment. :( Actually, the empty set should be included ultimately, but I was calling this function from another one that added the empty set so I didn't include it.

jonrsharpe Over a year ago

@AaronHall only three, apparently.

jonrsharpe Over a year ago

@mauve note that the itertools documentation includes equivalent implementations of both chain.from_iterable and combinations, so you don't necessarily have to import anything.

DNA · Accepted Answer · 2014-07-07 19:57:54Z

2

Here's one way, using recursion, though you can alternatively do it iteratively with a loop, and join the lists for each n:

a = [4,2]

def subseqs(x):
    def go(x, n):
        return zip(*(x[i:] for i in range(n))) + go(x, n-1) if n else []
    return go(x, len(x))

print subseqs(a)   # [(4, 2), (4,), (2,)]

or using a list comprehension:

print sum([zip(*(a[i:] for i in range(n))) for n in range(len(a)+1)], [])

edited Jul 7, 2014 at 19:57

answered Jul 7, 2014 at 19:36

DNA

42.7k12 gold badges114 silver badges153 bronze badges

3 Comments

mauve Over a year ago

This is so much closer than I was. I should have included an example with some duplicates - (4,2,2) should also return (2,2).

DNA Over a year ago

For [4,2,2] this code will return [(4, 2, 2), (4, 2), (2, 2), (4,), (2,), (2,)] - what result are you looking for?

mauve Over a year ago

Dangit, you're right. I need to figure out how to get (2,2) back for [2,4,2]

Collectives™ on Stack Overflow

Generate partial subsets in Python

2 Answers 2

5 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related