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 
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
Are you new to LinuxQuestions.org? Visit the following links:
Site Howto 
Site FAQ 
Sitemap 
Register Now
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQrelated cookies.

Introduction to Linux  A Hands on Guide
This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.
Click Here to receive this Complete Guide absolutely free. 


12282010, 10:27 PM

#1

LQ Newbie
Registered: Jun 2010
Location: boston & sf bay, depending on the day
Distribution: ubuntu, rhel, debian
Posts: 20
Rep:

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 nearcomplete 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



12302010, 02:15 AM

#2

Senior Member
Registered: Nov 2005
Distribution: Debian
Posts: 2,555

It kind of depends on how you define a "set":
So 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) ]



12312010, 12:54 AM

#3

LQ Newbie
Registered: Jun 2010
Location: boston & sf bay, depending on the day
Distribution: ubuntu, rhel, debian
Posts: 20
Original Poster
Rep:

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.



01022011, 04:46 AM

#4

Senior Member
Registered: Sep 2006
Location: Liverpool  England
Distribution: slackware64 13.37 and current, Dragonfly BSD
Posts: 1,810

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.



Thread Tools 
Search this Thread 


Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



All times are GMT 5. The time now is 05:52 PM.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.

Latest Threads
LQ News

