Python loop through list and return "out of sequence" values
Question: Consider this list:

    
    
    dates = [
        ('2015-02-03', 'name1'),
        ('2015-02-04', 'nameg'),
        ('2015-02-04', 'name5'),
        ('2015-02-05', 'nameh'),
        ('1929-03-12', 'name4'),
        ('2023-07-01', 'name7'),
        ('2015-02-07', 'name0'),
        ('2015-02-08', 'nameh'),
        ('2015-02-15', 'namex'),
        ('2015-02-09', 'namew'),
        ('1980-12-23', 'name2'),
        ('2015-02-12', 'namen'),
        ('2015-02-13', 'named'),
    ]
    

How can I identify those dates that are out of sequence. I don't care if they
repeat, or skip, I just need the ones way out of line. Ie, I should get back:

    
    
    ('1929-03-12', 'name4'),
    ('2023-07-01', 'name7'),
    ('2015-02-15', 'namex'),
    ('1980-12-23', 'name2'),
    

Namex is less obvious, but it's not in the general order of the list.

My simplistic start (which I have deleted to simplify the question) is
obviously woefully incomplete.

* * *

**Update** : Based on the comments, it seems an implementation of the [Longest
Increase
Subsequence](https://en.wikipedia.org/wiki/Longest_increasing_subsequence)
(LIS) will get me started, a python implementation found here:

  * <http://stackoverflow.com/a/9832414/1061836>
  * [How to determine the longest increasing subsequence using dynamic programming?](http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming)
  * <https://rosettacode.org/wiki/Longest_increasing_subsequence#Python>
  * <http://codereview.stackexchange.com/questions/10230/python-implementation-of-the-longest-increasing-subsequence>

Seems once I get the LIS, I can compare it to the original list and see where
the gaps are... Fascinating. SO is the hive-mind of awesomeness.


Answer: ## Short answer, general solution

Using my [answer to the "Longest increasing subsequence"
question](http://stackoverflow.com/a/38337443/1916449), this could be
implemented simply as:

    
    
    def out_of_sequence(seq):
      indices = set(longest_subsequence(seq, 'weak', key=lambda x: x[0], index=True))
      return [e for i, e in enumerate(seq) if i not in indices]
    

## Longer answer, specific solution

Based on the [question at Code
Review](http://codereview.stackexchange.com/q/10230/110989) and a [question
about non-decreasing sequences](http://stackoverflow.com/a/21718032/1916449)
(since that's what you're after), here's a solution to your problem:

    
    
    from bisect import bisect_right
    from operator import itemgetter
    
    
    def out_of_sequence(seq, key = None):
      if key is None: key = lambda x: x 
    
      lastoflength = [0] # end position of subsequence with given length
      predecessor = [None] # penultimate element of l.i.s. ending at given position
    
      for i in range(1, len(seq)):
        # find length j of subsequence that seq[i] can extend
        j = bisect_right([key(seq[k]) for k in lastoflength], key(seq[i]))
        # update old subsequence or extend the longest
        try: lastoflength[j] = i
        except: lastoflength.append(i)
        # record element preceding seq[i] in the subsequence for backtracking
        predecessor.append(lastoflength[j-1] if j > 0 else None)
    
      indices = set()
      i = lastoflength[-1]
      while i is not None:
        indices.add(i)
        i = predecessor[i]
    
      return [e for i, e in enumerate(seq) if i not in indices]
    
    
    print(*out_of_sequence(dates, itemgetter(0)), sep='\n')
    

Outputs:

    
    
    ('1929-03-12', 'name4')
    ('2023-07-01', 'name7')
    ('2015-02-15', 'namex')
    ('1980-12-23', 'name2')
    

* * *

The `key` parameter (inspired by
[`sorted`](https://docs.python.org/3.5/library/functions.html#sorted) builtin)
specifies a function of one argument that is used to extract a comparison key
from each list element. The default value is `None` so the caller has a
convenient way of saying "I want to compare the elements directly". If it is
set to `None` we use `lambda x: x` as an [identity
function](https://en.wikipedia.org/wiki/Identity_function), so the elements
are not changed in any way before the comparison.

In your case, you want to use the dates as keys for comparison, so we use
[`itemgetter(0)`](https://docs.python.org/3/library/operator.html#operator.itemgetter)
as `key`. And `itemgetter(1)` would use the names as `key`, see:

    
    
    >>> print(*map(itemgetter(1), dates))
    name1 nameg name5 nameh name4 name7 name0 nameh namex namew name2 namen named
    

Using `itemgetter(k)` is equivalent to `lambda x: x[k]`:

    
    
    >>> print(*map(lambda x: x[1], dates))
    name1 nameg name5 nameh name4 name7 name0 nameh namex namew name2 namen named
    

Using it with `map` is equivalent to a generator expression:

    
    
    >>> print(*(x[1] for x in dates))
    name1 nameg name5 nameh name4 name7 name0 nameh namex namew name2 namen named
    

But if we used a similar list comprehension to pass the sequence to
`out_of_sequence` we would get a different result from expected:

    
    
    >>> print(*out_of_sequence([x[0] for x in dates]), sep='\n')
    1929-03-12
    2023-07-01
    2015-02-15
    1980-12-23
    

Likewise, if we compare the date-name pairs directly we get wrong results
(because `'nameg'` compares greater to `'name5'`):

    
    
    >>> print(*out_of_sequence(dates), sep='\n')
    ('2015-02-04', 'nameg')
    ('1929-03-12', 'name4')
    ('2023-07-01', 'name7')
    ('2015-02-15', 'namex')
    ('1980-12-23', 'name2')
    

Because we want to return dates and names, and we want to order by dates only,
we need to pass a function that extracts dates using the `key` parameter.

An alternative would be to get rid of `key` and just write:

    
    
    j = bisect_right([seq[k][0] for k in lastoflength], seq[i][0])
    

But since this is stackoverflow, maybe one day another person will come by
this answer and will need some other key extraction, therefore I decided to
post the more general solution here.

