Ask Your Question
0

Gathering sublists based on functional programming (GatherBy)

asked 2012-11-02 06:13:50 -0600

PatB gravatar image

Hi, I'm looking at translating a very nice solution to the MrP and MrS puzzle. http://mathematica.stackexchange.com/...

The translation of the problem involves list comprehensions and functional programming. We can generate the tuples of solutions in the form:

possibilities = [ (i,j) for i in range(2,99) for j in range(2,i)]

Then we would like to group these possibilities into lists that have multiple factorizations... In this case informationFilter could be a lambda function for mrP: mrP = lambda a,b : a*b

I am having trouble finding an easy way to do the equivalent of the mathematica function: GatherBy:

GatherBy[possibilities, informationFilter]

So the question is: Given a list of tuples like : [(3, 2), (4, 2), (4, 3), (5, 2), (5, 3), (5, 4), (6, 2), (6, 3), (6, 4), (6, 5)... (98,97)]

How would you gather them into sublists such that their products are the same...

[(4,3),(6,2)] would be one valid sublist.

Many thanks for letting me "think out loud" on this one. Apologies in advance if the answer is trivial.

./pat

edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
3

answered 2012-11-02 13:12:34 -0600

Jason Grout gravatar image

updated 2012-11-02 13:15:14 -0600

How about using the groupby function?

a=[(3, 2), (4, 2), (4, 3), (5, 2), (5, 3), (5, 4), (6, 2), (6, 3), (6, 4), (6, 5), (98,97)]
from itertools import groupby
print [list(g) for k,g in groupby(sorted(a,key=prod),key=prod)]
print dict([(k,list(g)) for k,g in groupby(sorted(a,key=prod),key=prod)])

http://aleph.sagemath.org/?q=5e10542b...

edit flag offensive delete link more

Comments

+1 for groupby (more FP)

benjaminfjones gravatar imagebenjaminfjones ( 2012-11-02 16:04:27 -0600 )edit

Thanks for posting this solution as well, illustrating the sagesse that can be found when one looks to find equivalents.

PatB gravatar imagePatB ( 2012-11-02 17:16:16 -0600 )edit
2

answered 2012-11-02 06:30:46 -0600

Jesustc gravatar image

updated 2012-11-02 06:45:38 -0600

How about

sage: initial_list = [(3, 2), (4, 2), (4, 3), (5, 2), (5, 3),\
sage:                 (5, 4), (6, 2), (6, 3), (6, 4), (6, 5), (98,97)]
sage: sublists = []
sage: for product in list(set([a*b for a,b in initial_list])) :
sage:     sublists.append([pair for pair in initial_list if pair[0]*pair[1] == product])

Or, maybe, as a dictionary, with the products as keys:

sage: initial_list = [(3, 2), (4, 2), (4, 3), (5, 2), (5, 3),\
sage:                 (5, 4), (6, 2), (6, 3), (6, 4), (6, 5), (98,97)]
sage: products = list(set([a*b for a,b in initial_list]))
sage: sublists = dict([[product,[]] for product in products])
sage: for pair in initial_list :
sage:     product = pair[0]*pair[1]
sage:     sublists[product].append(pair)

EDIT:

Slightly faster method (only multiplying once):

sage: initial_list = [(3, 2), (4, 2), (4, 3), (5, 2), (5, 3),\
sage:                 (5, 4), (6, 2), (6, 3), (6, 4), (6, 5), (98,97)]
sage: sublists = dict()
sage: for pair in initial_list :
sage:     product = pair[0]*pair[1]
sage:     if not(product in sublists.keys()) :
sage:         sublists[product] = []
sage:     sublists[product].append(pair)

EDIT:

Even in a single line :)

sage: sublists = dict([[product,[pair for pair in initial_list if pair[0]*pair[1] == product]] for product in list(set([a*b for a,b in initial_list]))])

Yeah, I am having fun!

edit flag offensive delete link more

Comments

Hi Jesustc, I thought about the answer and came up with the 2nd approach, using the hash (perl speak) Interestingly, unlike sage/python, perl requires that the hash have a pointer (reference) to a list because perl does not natively supply objects. I am glad I'm switching to python!

PatB gravatar imagePatB ( 2012-11-02 17:07:49 -0600 )edit

Python is definitely fun! Though the solution of Jason Grout is definitely better (and probably more efficient too, I have not tested it), if one does not know the specific module to do it at best, it is easy to come up with a few possible solutions and to quickly prototype them :).

Jesustc gravatar imageJesustc ( 2012-11-02 22:48:55 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2012-11-02 06:13:50 -0600

Seen: 556 times

Last updated: Nov 02 '12