Питонический способ определить, смежны ли два заданных числа в целочисленной последовательности

Для целых чисел 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.

Что-то говорит мне, что есть более питонический способ сделать то или это, это хорошо изученная проблема, и я пропускаю более ясный / более чистый способ приблизиться к ней.

Используйте любой редуктор, чтобы определить, соответствует ли любая соседняя пара (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 

Проблема может быть разбита на две подзадачи:

  1. Преобразование последовательности в последовательность пар, например [a, b, c] должно быть преобразовано в [(a, b), (b, c)] .
  2. Определение того, находится ли данная пара (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)