Python: Sort a list according to two attributes

Question

I have a list of the following kind:

class Ind(object):
    def __init__(self,ID,mate):
        self.ID=ID
        self.mate=mate

population=[Ind(8,None), Ind(1,2), Ind(20,3), Ind(2,1), Ind(12,None), Ind(3,20), Ind(10,11), Ind(11,10)]

You can think of this list population as a population of individuals which all have an ID. Some of them have a mate (an individual who is present in the same population or the same list). The mate value is actually the ID of the mate! Therefore, if there is an instance of Ind which attributes ID equals 12 and mate equals 34, then there is necessarily an individual in the list whose ID equals 34 and whose mate equals 12. Individuals that do not have a mate have None in the mateattribute. Does it make sense?

I'd like to sort this list so that the first individual mates with the last one, the second individual mates with the second-to-last individual, etc... The individual which attribute mateequals None should stand in the middle of the list.

There are many possible outputs that fit what I want. Here is one example of these outputs for the above list:

population=[Ind(1,2), Ind(20,3), Ind(10,11), Ind(8,None), Ind(12,None), Ind(11,10), Ind(3,20), Ind(2,1)]

Answer 1

You can try something like this:

def custom_sort(population):
    pop_dict = { ind.ID: ind for ind in population }

    start = []
    nones = []
    end = []
    for ind in population:
        if ind.mate is None:
            nones.append(ind)
        elif pop_dict[ind.mate] not in start:
            start.insert(0, ind)
            end.append(pop_dict[ind.mate])
    return start + nones + end

This is under assumption that "being a mate" is a 1-to-1 relation.

Answer 2

You just need a key for the sorting function. The following example requires that individuals are monogamous and not married to themselves. It also requires that if (a,b) is listed, (b,a) is also listed. If these prerequisites are not met and Ind(2,1) can occur without Ind(1,2), this function will place Ind(2,1) towards the end of the list. The first index in the key function is the type: "first" in relationship (where IDmate) comes third. These first and second types are sorted in order by their ids; last type is sorted in reverse order by its mate.

def keyfun(x):
   if x.mate==None: 
     return (1,x.ID)
   elif x.ID<x.mate: 
     return (0,x.ID)
   else:
     return (2,-x.mate)

sorted(population,key=keyfun)

Another way to handle this, still assuming that if (a,b) is in the list (b,a) will also be in the list, is to just preprocess by removing (b,a) cases, then postprocess by adding them back in in reverse order.