LinuxQuestions.org
Support LQ: Use code LQ3 and save $3 on Domain Registration
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 12-28-2010, 09:27 PM   #1
robotsari
LQ Newbie
 
Registered: Jun 2010
Location: boston & sf bay, depending on the day
Distribution: ubuntu, rhel, debian
Posts: 20

Rep: Reputation: 1
Discussion - Python List Comprehensions; power set?


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
 
Old 12-30-2010, 01:15 AM   #2
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian
Posts: 2,445

Rep: Reputation: 829Reputation: 829Reputation: 829Reputation: 829Reputation: 829Reputation: 829Reputation: 829
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) ]
 
Old 12-30-2010, 11:54 PM   #3
robotsari
LQ Newbie
 
Registered: Jun 2010
Location: boston & sf bay, depending on the day
Distribution: ubuntu, rhel, debian
Posts: 20

Original Poster
Rep: Reputation: 1
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.
 
Old 01-02-2011, 03:46 AM   #4
bgeddy
Senior Member
 
Registered: Sep 2006
Location: Liverpool - England
Distribution: slackware64 13.37 and -current, Dragonfly BSD
Posts: 1,810

Rep: Reputation: 227Reputation: 227Reputation: 227
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.
 
  


Reply

Tags
python


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
DISCUSSION: Power to the Users - part 3 stomfi LQ Articles Discussion 1 07-29-2006 04:10 AM
set iBook to automatically power-up after power failure peachy Other *NIX 4 04-19-2006 12:44 PM
DISCUSSION: Power to the Users - part 1 stomfi LQ Articles Discussion 1 04-01-2006 10:05 PM
DISCUSSION: Power to the Users - Part 7 stomfi LQ Articles Discussion 0 04-01-2006 10:59 AM


All times are GMT -5. The time now is 11:13 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration