CODEWITHSUNDEEP
pythonpython-2.7
mauve
mauve

Reputation: 2763

Generate partial subsets in Python

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

Upvotes: 2

Views: 220

Answers (2)

jonrsharpe
jonrsharpe

Reputation: 121987

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.

Upvotes: 3

DNA
DNA

Reputation: 42597

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)], [])

Upvotes: 2

Related Questions