Discussion

robotsari · 12-28-2010, 09:27 PM

Hi,

I teach an introductory programming class in Python and the staff and I are trying to stump each other with some "challenge" list comprehension problems to give to our students as a fun optional problem.

I'd love your take - can you think of any tricky ones?

Additionally, we've been debating if you can generate a power set from a single list comprehension. I've come kind of close but always miss a few. Can anyone prove either side of the debate? (it would suffice to be able to generate a near-complete powerset, eg one that omits the empty set [] or generally gives 2**n - 1 elements)

Thanks all, I look forward to reading your responses.

Sarina

ntubski · 12-30-2010, 01:15 AM

It kind of depends on how you define a "set":

Quote:

Suppose that some (possibly countably infinite) universe of discourse for sets is mapped into the non-negative integers. Then a set can be represented as a bit vector; an element is in the set if the bit whose index corresponds to that element is a one-bit.

Common Lisp the Language, 2nd Edition
12.7. Logical Operations on Numbers

So

Code:

 range(2**s)

gives a power set. If you want the sets explicitly represented as lists a nested list comprehension is required (which probabably doesn't count as a "single list comprehension"):

Code:

[ [ x for x in range(int(floor(log(max(n,1)) / log(2) + 1))) if (1 << x) & n ]
  for n in range(2**5) ]

or more readably:

Code:

from math import log, floor

def bits(n):
    return int(floor(log(max(n,1)) / log(2) + 1))

def set_from_int(n):
    return [ x for x in range(bits(n)) if (1 << x) & n ]

def power_set(s):
    return [ set_from_int(n) for n in range(2**s) ]

robotsari · 12-30-2010, 11:54 PM

Agreed I phrased the problem incorrectly.

By "power set" we mean to define the problem as follows:

Given a list of numbers my_list = [1, 2, 3, 4], can you give a list comprehension that generates all possible subsets of my_list?

So the list comprehension you gave is the basic idea. We have not visited this problem again since I posted the question but will update if one of us thinks of an elegant solution, or comes up with another fun challenge problem.

bgeddy · 01-02-2011, 03:46 AM

Quote:

Given a list of numbers my_list = [1, 2, 3, 4], can you give a list comprehension that generates all possible subsets of my_list?

I'm not sure if I understand your concept of subsets of the list. The following provides a list of all possible combinations of length between 1 and the length of the list stored as tuples. I use the itertools module to make finding combinations easy and run a nested list comprehension.

Code:

import itertools
my_list=[1,2,3,4,5]
power_set=[result for number in range(1,len(my_list)+1) for result in itertools.combinations(my_list,number)]
print power_set

Hope that's useful. Personally I'd tend to use loops when list comprehensions become a bit tricky like this but each to his own.