1

I have a list of dictionaries (actually, a list of objects containing dictionaries) like this, representing a table:

rows = [
  { '11': 14,  '12':  0,  '13':  0,  '14': 20 },
  {                       '13':  8            },
  { '11':  7,                                 },
  { '11':  2,                        '14':  2 },
  {            '12':  2,  '13':  2            },
  { '11':  3,                        '14':  3 },
  { '11':  1,                        '14':  1 },
  {                       '13':  5            },
  { '11':  8,                                 },
  { '11':  0,                        '14':  0 },
  { '11':  9,                                 },
  {                                  '14': 10 },
  {                       '13': 19            },
  {                                  '14': 12 },
  {                       '13': 15            },
  {            '12':  3,  '13':  3            }
]

I want to sort them by each column in the table like this:

[
  { '11':  0,                        '14':  0 },
  { '11':  1,                        '14':  1 },
  { '11':  2,                        '14':  2 },
  { '11':  3,                        '14':  3 },
  {                                  '14': 10 },
  {                                  '14': 12 },
  { '11':  7                                  },
  { '11':  8                                  },
  { '11':  9                                  },
  { '11': 14,  '12':  0,  '13':  0,  '14': 20 },
  {            '12':  2,  '13':  2            },
  {            '12':  3,  '13':  3            },
  {                       '13':  5            },
  {                       '13':  8            },
  {                       '13': 15            },
  {                       '13': 19            }
]

There are a few possible 'correct' orders, but that's one of them.

I've seen and tried various solutions for this sort of thing, but they all seem to involve placing None at the beginning or end of the list, which I don't want. For example:

rows.sort(key=lambda r: [r.get(c, 0) for c in ['11', '12', '13', '14']])

There are certain items that can't be compared (because they have no keys in common), but a comparison function can't return 'I don't know', can it?

I'm using Python 3.5, but it would be nice to stay compatible with 2.7 and 3.4.

Josh Goodwin
  • 181
  • 1
  • 6
  • The logic you're describing is a partial order. Sorting requires a total order. It's not well defined on partially ordered data. I don't think there's an easy way around that. – Blckknght Aug 22 '16 at 17:52
  • This is an interesting puzzle. I will see if I can think of a good solution. – Mad Physicist Aug 22 '16 at 18:35
  • 1
    Would it be acceptable for the elements with `'14': 10` and `'14': 12` to appear anywhere else as long as it is before `'14': 20`? – Mad Physicist Aug 22 '16 at 18:37
  • Yes, @MadPhysicist – Josh Goodwin Aug 22 '16 at 18:55
  • The source data is actually in the form of a some linked lists (one per column). Having looked at topological sorting, I wonder if I should take a few steps back and take advantage of this. – Josh Goodwin Aug 22 '16 at 19:06
  • I don't understand the rules of your sort. How did '14': 12 come after '11': 3 and before '11': 7? Why are the '12' and '13' keys ranked last? In general though, of course a comparison function can handle None. You just decide where None comes in the ordering, and write the comparison function to put it there. – Kenny Ostrom Aug 22 '16 at 20:52
  • There is no why, @KennyOstrom - as I say, there are several possible correct orders, the data is only partially ordered. – Josh Goodwin Aug 22 '16 at 22:18
  • Okay, got it. For all elements A and B, and all keys i, if A[i] < B[i] then A – Kenny Ostrom Aug 23 '16 at 14:47

0 Answers0