4

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)]
3
  • is there a requirement to actually sort the result as well?
    – user3850
    Aug 26, 2013 at 15:26
  • 2
    Looking at your example, it seems an Individual can have two different mates : there's Ind(2,3) (2 mates with 3) and Ind(2, 1) (2 mates with 1). Is this a typo ? Or is mating really a one-to-many relationship in your population? Aug 26, 2013 at 15:31
  • Indeed there was a mistake in my example. Sorry about that. I corrected it!
    – Remi.b
    Aug 26, 2013 at 15:33

4 Answers 4

5

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.

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

1
  • You're right...I don't know why I was thinking otherwise. Edited :) Aug 26, 2013 at 17:38
0

How about this. Split list into three lists, one with ID < mate, the second with ID > mate, and the third with mate is None. Then, concatenate the sorted lists, each sorted via ID.

I've added a __repr__ method to the Ind class for output readability.

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

    def __repr__(self):
        return 'Ind({},{})'.format(self.ID,self.mate)

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

def custom_sort(pop):
    singles, less, more = [], [], []
    for p in pop:
        if p.mate is None:
            singles.append(p)
        elif p.ID < p.mate:
            less.append(p)
        elif p.ID > p.mate:
            more.append(p)
    comp = lambda x,y: cmp(x.ID,y.ID)
    return sorted(less,cmp=comp) + sorted(singles,cmp=comp) + sorted(more,cmp=comp,reverse=True)


print custom_sort(population)

This outputs:

[Ind(1,2), Ind(2,3), Ind(10,11), Ind(8,None), Ind(12,None), Ind(11,10), Ind(3,2), Ind(2,1)]
0

There is a lot you can do with costum key functions:

def my_key(ind):
    if ind.mate is None:
        return 0
    if ind.ID < ind.mate:
        return -ind.ID - 1
    else:
        return ind.mate + 1
population.sort(key=my_key)

This assumes that IDs will never be negative. If IDs are always greater than 0, you can discard the - 1 and + 1.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.