Python遍历列表并返回“无序”值

Question

考虑以下列表：

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'),
]

我该如何识别那些不按顺序排列的日期呢。我不在乎他们是重复，还是跳过，我只需要一个越界的方法。也就是说，我应该回去：

^{pr2}$

Namex不那么明显，但它不在列表的一般顺序中。在

我简单化的开始（为了简化问题，我删除了它）显然是不完整的。在

---

更新：根据评论，似乎Longest Increase Subsequence（LIS）的实现可以让我开始，这里有一个python实现：

• https://stackoverflow.com/a/9832414/1061836
• How to determine the longest increasing subsequence using dynamic programming?
• https://rosettacode.org/wiki/Longest_increasing_subsequence#Python
• https://codereview.stackexchange.com/questions/10230/python-implementation-of-the-longest-increasing-subsequence

似乎一旦我得到了LIS，我就可以把它和原始列表进行比较，看看差距在哪里。。。迷人的。令人敬畏的蜂巢思维也是如此。在

Answer 1

简答，通解

使用my answer to the "Longest increasing subsequence" question，这可以简单地实现为：

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]

更长的答案，具体的解决方案

基于question at Code Review和question about non-decreasing sequences（因为这正是您所追求的），下面是您的问题的解决方案：

^{pr2}$

输出：

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

---

key参数（受^{}内置函数的启发）指定一个由一个参数组成的函数，用于从每个列表元素中提取比较键。默认值是None，因此调用者可以方便地说“我想直接比较元素”。如果它被设置为None，我们使用lambda x: x作为identity function，因此在比较之前元素不会以任何方式更改。在

在您的例子中，您希望使用日期作为比较键，因此我们使用^{}作为key。并且itemgetter(1)将使用key的名称，请参见：

^{4}$

使用itemgetter(k)等同于lambda x: x[k]：

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

将其与map一起使用相当于生成器表达式：

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

但是，如果我们使用类似的列表理解将序列传递给out_of_sequence，我们将得到与预期不同的结果：

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

同样，如果我们直接比较日期名称对，我们会得到错误的结果（因为'nameg'比'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')

因为我们要返回日期和名称，而且只想按日期排序，所以需要传递一个使用key参数提取日期的函数。在

另一种方法是去掉key，只写：

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

但是由于这是stackoverflow，也许有一天另一个人会得到这个答案，并且需要一些其他的密钥提取，因此我决定在这里发布更一般的解决方案。在

Answer 2

如果当前日期大于上一个有效日期，这将为您建立一个新的锚定日期。在

import arrow

out_of_order = []
anchor_date = arrow.get(dates[0][0])
for dt, name in dates:
  if arrow.get(dt) < anchor_date:
    out_of_order.append((dt, name))
  else:
    anchor_date = arrow.get(dt)