# Gathering sublists based on functional programming (GatherBy)

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 close merge delete

Sort by ยป oldest newest most voted

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

more

+1 for groupby (more FP)

( 2012-11-02 16:04:27 -0500 )edit

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

( 2012-11-02 17:16:16 -0500 )edit

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!

more

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!

( 2012-11-02 17:07:49 -0500 )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 :).

( 2012-11-02 22:48:55 -0500 )edit