检查列表是否按自定义顺序

Question

我正在尝试验证列表说：

X = ['a','c', 'c', 'b', 'd','d','d']

针对自定义排序列表：

Y = ['a',b','d']

在这种情况下，X 针对 Y 验证应该 return True 而不管其中的额外元素和重复项，只要它符合 Y 中的顺序并且至少包含两个元素。

案例：

X = ['a','b'] # Returns True
X = ['d','a', 'a', 'c','b'] # Returns False
X = ['c','a','b', 'b', 'c'] # Returns True

我现在最多只能删除重复项和多余元素。我没有尝试使用自定义列表对它们进行排序。我只需要验证订单。我所做的或至少尝试过的是创建一个字典，其中的值是订单的索引。谁能指出我正确的方向？

Answer 1

从 X 创建一个新列表，其中仅包含 Y 中没有重复的元素。然后，类似地，从 Y 中删除 X 中不包含的所有元素并进行重复数据删除。那么你的检查只是一个简单的相等性检查。

def deduplicate(iterable):
    seen = set()
    return [seen.add(x) or x for x in iterable if x not in seen]

def goes_with_order(X, Y):
    Xs = set(X); Ys = set(Y)
    X = deduplicate(x for x in X if x in Ys)
    Y = deduplicate(y for y in Y if y in Xs)
    return X == Y

Answer 2

from itertools import zip_longest, groupby

okay = list(x == y for y, (x, _) in zip_longest(
        (y for y in Y if y in X), groupby(x for x in X if x in Y)))
print(len(okay) >= 2 and all(okay))

首先我们从两个列表中丢弃不必要的元素。然后我们可以使用 groupby 折叠 X 相同元素的序列。例如，您的第一个示例 ['a', 'c', 'c', 'b', 'd', 'd', 'd'] 首先变为 ['a', 'c', 'c', 'b'] (by discarding the unnecessary'd'), then[('a', _), ('c', _), ( 'b', _)]。如果我们逐个元素地比较它的键与 Y 没有不必要的位，并且至少有 2 个，我们有一个匹配项。如果顺序被违反了（比如['b', 'c', 'c', 'a', 'd', 'd', 'd']，本来okay里面有一个False，就会失败，如果某处多出一个元素，就会和[=进行比较20=]（多亏了 zip_longest），False 又会出现在 okay.

这可以通过使用集来加速成员查找来改进。

检查列表是否按自定义顺序

Check if a list is in a custom order

list

python-3.x

python-3.6