[РЕДАКТИРОВАТЬ] Хорошо, я тупой.Очевидно, это можно сделать еще проще:
def compatible_ordering(xs, ys):
return all(
y1 <= y2
for (_, y1), (_, y2) in pairwise(sorted(izip(xs, ys)))
)
[/ EDIT]
Вот решение O (n * log n):
from itertools import izip, tee
def pairwise(iterable):
a, b = tee(iterable)
next(b)
return izip(a, b)
def compatible_ordering(xs, ys):
return all(
x1 == x2 or y1 <= y2
for (x1, y1), (x2, y2) in pairwise(sorted(izip(xs, ys)))
)
Это в основномодин вкладыш, если не считать рецепт pairwise() от itertools .Чувак, ты должен любить Python за это.
Кстати, обратите внимание на сходство с неправильным решением в конце.
Как это работает, может быть легче объяснить, если мы переписаем алгоритм в болеепроцедурная форма:
def compatible_ordering(xs, ys): # line 0
xys = zip(xs, ys) # line 1
xys.sort() # line 2
for (x1, y1), (x2, y2) in pairwise(xys): # line 3
if x1 < x2 and y1 > y2: # line 4
return False # line 5
return True # line 6
На этот раз мы не пытаемся выяснить, выполняется ли условие для всех элементов (= success ), но вместо этого выполняется условие для некоторого элемента (= Ошибка ), поэтому формула тестирования в основном сводится на нет.
Теперь для каждой пары соседних кортежей ((x1, y1), (x2, y2)):
Всегда x1 <= x2, так как мы отсортировали их таким образом.Это означает, что если x1 != x2, то x1 < x2.
Если x1 == x2, мы знаем, что y1 <= y2, опять же, потому что мы их отсортировали.
Если x1 < x2 и y1 <= y2, оба (x1, x2) и (y1, y2) имеют одинаковый порядок, и мы продолжаем.
В противном случае, если x1 < x2 и y1 > y2наши два списка имеют несовместимые упорядочения, и мы return False.
Если мы закончили итерацию и не обнаружили несовместимости, мы return True.
IOW: сортировка создает порядок для ys, определяемый xs и самим ys для равных элементов в xs (поскольку равные элементы xs не налагают никакого порядкана ys).Тогда все, что нам нужно сделать, это проверить, действительно ли заказано ys.
Вот пример.После строки 0 у нас есть, например:
xs == [4, 3, 4, 2, 5, 4, 0, 2, 0, 5]
ys == [4, 1, 5, 1, 5, 5, 2, 2, 1, 3]
В строке 2 мы архивируем их и получаем:
xys == [(4, 4), (3, 1), (4, 5), (2, 1), (5, 5), (4, 5), (0, 2), (2, 2), (0, 1), (5, 3)]
В строке 3 мы сортируем:
xys == [(0, 1), (0, 2), (2, 1), (2, 2), (3, 1), (4, 4), (4, 5), (4, 5), (5, 3), (5, 5)]
ВВ строке 4 мы перебираем все пары соседних кортежей отсортированного списка и тестируем в строке 5:
x1 y1 x2 y2 x1 x2 y1 y2
( 0 , 1 ), ( 0 , 2 ) --> 0 < 0 and 1 > 2 --> False --> continue
( 0 , 2 ), ( 2 , 1 ) --> 0 < 2 and 2 > 1 --> True --> return False
КСТАТИ # 2: вполне возможно, что эта версия быстрее, чем oneliner.
[EDIT]
Ниже был мой первый и НЕПРАВИЛЬНЫЙ ответ на вопрос ОП.Тем не менее, я не удаляю его, как пример того, что происходит, если вы публикуете без прочтения.
Вот решение O (n):
def compatible_ordering(xs, ys):
return all(
(x1 <= x2) == (y1 <= y2)
for (x1, x2), (y1, y2) in izip(pairwise(xs), pairwise(ys))
)