Проверьте, находится ли список в произвольном порядке - PullRequest
Новая
       8

Проверьте, находится ли список в произвольном порядке

1 голос
/ 20 сентября 2019

Я пытаюсь подтвердить список, скажем:

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

по заказному заказному списку:

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

В этомпроверенный для Y регистр X должен возвращать True независимо от дополнительных элементов и дубликатов в нем, если он соответствует порядку в Y и содержит как минимум два элемента.

Примеры случаев: 

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

Самое большее, что я могу сейчас сделать, - это удалить дубликаты и лишние элементы.Я не пытаюсь сортировать их, используя пользовательский список.Мне просто нужно подтвердить заказ.То, что я сделал или, по крайней мере, попытался, это создать словарь, где значение является индексом заказа.Кто-нибудь может указать мне правильное направление?

Ответы [ 2 ]

1 голос
/ 20 сентября 2019 
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'], было бы False в okay, и он потерпел бы неудачу. Если где-то появился дополнительный элемент, было бы сравнение с None (благодаря zip_longest) и снова False был бы в okay.

Это можно улучшить, используя наборы для ускорения поиска членства.

0 голосов
/ 20 сентября 2019

Создайте новый список из 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
...