Питонический способ определить, смежны ли два заданных числа в целочисленной последовательности
Для целых чисел a, b таких, что a <b; и некоторая упорядоченная итеративная последовательность целых чисел, seq
. Определите, являются ли a
и b
соседними, в этом порядке, где-нибудь в seq
Очевидный первый проход:
предположим, что a <b (если a> b, просто значения переключения).
>>> idx = 0 >>> for i in range(0, len(l)): ... if a == l[i]: ... idx = i ... >>> b == l[idx+1]
Это кажется неуклюжим.
Например, данный
>>> [1, 2, 3, 8]
Если a равно 1 и b равно 3, они не смежны, если a равно 3 в b, равно 8.
Что-то говорит мне, что есть более питонический способ сделать то или это, это хорошо изученная проблема, и я пропускаю более ясный / более чистый способ приблизиться к ней.
- Найти уникальный элемент в неупорядоченном массиве, состоящем из дубликатов
- Обнаружение края для изображения, хранящегося в матрице
- Счетчик появления числа в Python
- Алгоритм Дейкстры в python
- Поиск мотивов с помощью пробоотборника Гиббса
Используйте любой редуктор, чтобы определить, соответствует ли любая соседняя пара (a, b):
>>> seq = [1, 2, 3, 8] >>> a = 3 >>> b = 8 >>> any((seq[i], seq[i+1]) == (a,b) for i in range(len(seq)-1)) True >>> b = 1 >>> any((seq[i], seq[i+1]) == (a,b) for i in range(len(seq)-1)) False >>>
Очень короткий ответ с использованием zip :
(a, b) in zip(seq[:-1], seq[1:])
Это работает, когда вам разрешено переворачивать
(a, b) in zip(seq[:-1], seq[1:]) or (b, a) in zip(seq[:-1], seq[1:])
Чтобы сделать это логически правильным, вы можете сначала выполнить проверку на a in seq
. Если он проходит, то предыдущий тест (ы) должен выполняться.
Некоторая информация о том, что делает zip
>>> print seq [1, 2, 3, 8] >>> zip(seq[:-1], seq[1:]) [(1, 2), (2, 3), (3, 8)]
Использование izip и islice из пакета itertools
from itertools import izip, islice N = len(seq) (a, b) in izip(islice(seq, 0, N - 1), islice(seq, 1, N))
Вы можете выполнять итерацию через пары элементов в последовательности и проверить, состоит ли пара из a
и b
. Используя itertools
рецепт из itertools
:
>>> from itertools import tee >>> def pairwise(iterable): ... x, y = tee(iterable) ... next(y, None) ... return zip(x, y) ... >>> a, b, seq = 3, 8, [1, 2, 3, 8] >>> (a, b) in pairwise(seq) True
Это будет работать быстро для произвольных больших последовательностей (в отличие от решений для разрезания списка).
Использование бинарного поиска будет самым быстрым.
Следующая реализация должна быть довольно быстрой, будет работать, даже если b > a
, в несортированных списках и если a
и / или b
не присутствуют в списке (в этом случае вернет False
):
from bisect import bisect_left def is_adjacent(a, b, l): ind = bisect_left(l,a) if ind >= len(l): return False if l[ind] == a and l[ind+1] == b: return True else: return is_adjacent(a,b,l[ind+1:]) # eg is_adjacent(1, 3, [1, 2, 3, 8]) # gives False is_adjacent(3, 8, [1, 2, 3, 8]) # gives True
Все остальные реализуют нечто совершенно отличное от того, что говорит определение проблемы для реализации. В частности, мы должны сделать следующее:
Определим, если
a == l[i]
влечетb == l[i+1]
гдеi < len(l)
Это не требует, чтобы a
или b
даже присутствовал в списке, и (если «упорядоченный» не означает «сортировка»), a
и b
могут отображаться несколько раз в списке.
Чтобы определить, что на самом деле говорит определение задачи, мы можем пройти через все пары соседних элементов и проверить, выполняется ли импликация:
if l and l[-1] == a: # Problem definition doesn't say what to do. shrug() return all(x != a or y == b for (x, y) in zip(l[:-1], l[1:]))
Если мы предполагаем, что вход отсортирован, мы можем сделать лучше с двоичным поиском:
import bisect if l and l[-1] == a: # We still don't know what to do for this case. shrug() possible_leftmost_a_index = bisect.bisect_left(l, a) if possible_leftmost_a_index == len(a): # All elements of l are lower than a. return True elif l[possible_leftmost_a_index] != a: # a isn't in the list. return True elif l[possible_leftmost_a_index+1] == b: # The implication holds. (We don't have to look for more occurrences of a, # because bisect guarantees no a occurrences to the left, and everything to # the right is greater than a.) return True else: return False
Проблема может быть разбита на две подзадачи:
- Преобразование последовательности в последовательность пар, например
[a, b, c]
должно быть преобразовано в[(a, b), (b, c)]
. - Определение того, находится ли данная пара
(x, y)
в последовательности, сгенерированной на шаге 1.
Вы можете преобразовать итерабельную последовательность в пары:
def pairs(collection): collection = iter(collection) a = next(collection) for b in collection: yield a, b a = b
collection
может быть списком или даже бесконечным генератором.
Чтобы определить, есть ли (x, y)
в выводе pairs
вам просто нужно сделать:
(x, y) in pairs(seq)
- Простой способ сплавления нескольких близких точек?
- Моя реализация слияния двух отсортированных списков в линейном времени – что можно улучшить?
- цикл от начала до конца
- Среднее лицо – алгоритм
- Перестановки без повторения вывода в Python
- Структура данных Python для индексируемого списка строк
- Minimax: как я могу реализовать его в Python?
- Обозначение Big-O для двух простых рекурсивных функций
- Алгоритм. Как эффективно удалять повторяющиеся элементы в списке?