Organizing a Python list of lists as function of number of occurances

Question

I am having a Python list of lists, that I get as an output of python-igraph (membership to clusters). The integers represent an association of a vertex to a certain cluster at a certain subgraph. I would like to organise this list in a way that the biggest cluster in the whole (unconnected) graph is getting the lowest integer - 0, and then the smaller the cluster the higher the integer that is assigned to it. For now I do it in a very cumbersome way:

import numpy as np
def organize_in_decreasing_order(membership_list):
 conlist = np.concatenate(membership_list)
 count=np.bincount(conlist)
 ordered_list = []
 for i in range(len(count)):
 ordered_list.append(np.argmax(count))
 count[np.argmax(count)]=0
# print ordered_list
 maxvalue = max(conlist)
 locations = []
 for number in range(maxvalue+1):
 locs = []
 for i in range(len(membership_list)):
 for j in range(len(membership_list[i])):
 if membership_list[i][j]==number:
 locs.append((i,j))
 locations.append(locs)
 for i,value in enumerate(ordered_list):
 for location in locations[value]:
 membership_list[location[0]][location[1]]=i
 return membership_list 

You can check it over the following list:

memlist = 
[[0,
 1,
 2,
 1,
 3,
 3,
 1,
 4,
 1,
 4,
 5,
 5,
 4,
 4,
 5,
 5,
 3,
 6,
 7,
 5,
 0,
 2,
 5,
 6,
 7,
 4,
 4,
 5,
 1,
 1,
 2,
 2,
 8,
 2,
 4,
 2,
 2,
 2,
 7,
 5,
 2,
 2,
 5,
 2,
 2,
 7,
 7,
 2,
 5,
 5,
 2,
 5,
 3,
 8,
 8,
 2,
 5,
 5,
 7,
 4,
 8,
 8,
 8,
 4,
 8,
 5,
 8,
 8,
 6,
 5,
 5,
 5,
 4,
 2,
 4,
 7,
 4,
 7,
 5,
 8,
 5,
 5,
 5,
 4,
 5,
 5,
 5,
 2,
 5,
 4,
 4],
 [9, 9, 9],
 [10],
 [11],
 [12]]

If you have an idea how to do it more efficiently I will be happy to hear!

• Colonel Beauvel: what's your input? what is the output? this long array?
• Christian K.: You want to order an array by the length of it's members? Then this should do it: sorted(a,key=len,reverse=True) where a is the nested array.
• Austin Hastings: You use memlist but I don't see it defined. Should that be membership_list?
• Ohm: @ColonelBeauvel Yes, the long array is the input
• Christian K.: If I use memlist as input I do not see any pattern in the output apart from the fact that the output list is ordered with respect to the length of its members. Does the function yield the correct output?

Answer 1

Try this code:

def organize_in_decreasing_order(membership_list):
 conlist = np.concatenate(membership_list)
 count = np.bincount(conlist)
 ordered_list = np.argsort(count)[::-1]
 lookup = np.argsort(ordered_list)
 return [[lookup[i] for i in sublist] for sublist in membership_list]

Be aware that the function above returns the organized list, but - in contrast to your implementation - does not change the input argument. You should also be aware that when count has repeated elements, the lists yielded by both implementations may not coincide. The reason for the different behaviour is that ties are dealt with differently.