CODEWITHSUNDEEP
pythonalgorithm
fiacre
fiacre

Reputation: 1180

Pythonic way to determine if two given numbers are adjacent in integer sequence

Given integers a, b such that a < b; and some ordered iterable sequence of integers, seq. Determine whether a and b appear adjacent, in that order, anywhere in seq

The obvious first pass is :

assume a < b (if a > b, just switch values).

>>> idx = 0
>>> for i in range(0, len(l)):
...     if a == l[i]:
...             idx = i
... 
>>> b == l[idx+1]

This feels clumsy.

For example, given 

>>> [1, 2, 3, 8]

If a is 1 and b is 3, they are not adjacent, if a is 3 in b is 8, they are.

Something tells me there is a more pythonic way of doing this or that this is a well explored problem, and I am missing a clearer/cleaner way to approach it.

Upvotes: 2

Views: 1613

Answers (6)

Elmex80s
Elmex80s

Reputation: 3504

Very short answer using zip:

(a, b) in zip(seq[:-1], seq[1:])

This works when you are allowed to flip

(a, b) in zip(seq[:-1], seq[1:]) or (b, a) in zip(seq[:-1], seq[1:])

To make it logically correct you can test for a in seq first. If it passes then the previous test(s) should hold.

Some info on what the zip is doing

>>> print seq 
[1, 2, 3, 8]
>>> zip(seq[:-1], seq[1:])
[(1, 2), (2, 3), (3, 8)]

Using izip and islice from the itertools package

from itertools import izip, islice
N = len(seq)
(a, b) in izip(islice(seq, 0, N - 1), islice(seq, 1, N))

Upvotes: 3

Greg Navis
Greg Navis

Reputation: 2934

The problem can be broken down into two subproblems:

  1. Converting a sequence into a sequence of pairs, e.g. [a, b, c] should be converted to [(a, b), (b, c)].
  2. Determining whether a given pair (x, y) is in the sequence generated in step 1.

You can convert an iterable to a sequence of pairs with:

def pairs(collection):
    collection = iter(collection)
    a = next(collection)
    for b in collection:
        yield a, b
        a = b

collection can be a list or even an infinite generator.

To determine whether (x, y) is in the output of pairs you just need to do:

(x, y) in pairs(seq)

Upvotes: 1

user2357112
user2357112

Reputation: 281576

Everyone else is implementing something entirely different from what the problem definition says to implement. Specifically, we're supposed to do the following:

Determine if a == l[i] implies b == l[i+1] where i < len(l)

That doesn't require a or b to even be in the list, and (if "ordered" isn't intended to mean "sorted") a and b could show up multiple times in the list.

To determine what the problem definition actually says to determine, we can go through all pairs of adjacent elements and test whether the implication holds:

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:]))

If we are supposed to assume the input is sorted, we can do better with a binary search:

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

Upvotes: 1

j-i-l
j-i-l

Reputation: 10977

Using binary search will be fastest.

The following implementation should be rather fast, will work even if b > a, on unsorted lists and if a and/or b are not present in the list (will return False in this case):

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:])

# e.g.
is_adjacent(1, 3, [1, 2, 3, 8])  # gives False
is_adjacent(3, 8, [1, 2, 3, 8])  # gives True

Upvotes: 2

Eugene Yarmash
Eugene Yarmash

Reputation: 150011

You could iterate through pairs of the elements in the sequence and check if a pair consists of a and b. Using the pairwise recipe from 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

This will work fast for arbitrary large sequences (unlike list slicing solutions).

Upvotes: 2

Prune
Prune

Reputation: 77850

Use the any reducer to determine whether any adjacent pair matches (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
>>>

Upvotes: 3

Related Questions