Finding consecutive numbers from multiple lists in python

Question

Consider, for example, that I have 3 python lists of numbers, like this:

a = [1,5,7]
b = [2,6,8]
c = [4,9]

I need to be able to check if there are consecutive numbers from these lists, one number from each list, and return true if there are.

In the above example, 7 from list a, 8 from list b and 9 from list c are consecutive, so the returned value should be true.This should be extendable to any number of lists (the number of lists is not known in advance, because they are created on the fly based on prior conditions).

Also, values in a list is not present in any other list. For example, list a above contains the element '1', so '1' is not present in any other list.

Is there a way to accomplish? It seems simple, yet too complex. I am a python newbie, and have been trying all sorts of loops but not even getting close to what I am looking for.

Looking for suggestions. Thanks in advance.

UPDATE: Here is the context for this question.

I am trying to implement a 'phrase search' in a sentence (which is part of a much bigger task).

Here is an example.

The sentence is: My friend is my colleague.

I have created an index, which is a dictionary having the word as the key and a list of its positions as the value. So for the above sentence, I get:

{
'My': [0,3],
'friend': [1],
'is': [2],
'colleague': [4]
}

I need to search for the phrase 'friend is my' in the above sentence.

So I am trying to do something like this:

First get the positions of words in the phrase from the dictionary, to get:

{
'My': [0,3],
'friend': [1],
'is': [2],
}

Then check if the words in my phrase have consecutive positions, which goes back to my original question of finding consecutive numbers in different lists.

Since 'friend' is in position 1, 'is' is in position 2, and 'my' is in position 3. Hence, I should be able to conclude that the given sentence contains my phrase.

Answer 1

Can you assume

• lists are sorted?
• O(n) memory usage is acceptable?

As a start, you could merge the lists and then check for consecutive elements. This isn't a complete solution because it would match consecutive elements that all appear in a single list (see comments).

from itertools import chain, pairwise

# from https://docs.python.org/3/library/itertools.html#itertools-recipes
def triplewise(iterable):
    "Return overlapping triplets from an iterable"
    # triplewise('ABCDEFG') --> ABC BCD CDE DEF EFG
    for (a, _), (b, c) in pairwise(pairwise(iterable)):
        yield a, b, c


def consecutive_numbers_in_list(*lists: list[list]) -> bool:
    big_list = sorted(chain(*lists))
    for first, second, third in triplewise(big_list):
        if (first + 1) == second == (third - 1):
          return True
    return False

consecutive_numbers_in_list(a, b, c)
# True

Note itertools.pairwise is py 3.10

If the lists are sorted but you need constant memory, then you can use an n pointer approach in which you have a pointer to the first element of each list, then advance the lowest pointer on each iteration and keep track of the last three values seen at all times.

Ultimately, your question doesn't make that much sense, in that this doesn't seem like a typical programming task. If you are a newbie to programming, you can ask what you are trying to accomplish, instead of how to implement your candidate solution, and we might be able to suggest a better method overall. See https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem

UPDATE

You are implementing phrase search. So an additional requirement, compared to the original question, is that the first list contain the first index of the sequence, the second list contain the second index of the sequence, etc. (As I assume that "friend my is" is not an acceptable search result for the query "my friend is".)

Pseudocode:

for each index i in the j=1th list:
  for each list from the jth list to the nth list:
    see whether i + j - 1 appears in list j

Depending on the characteristics of your data, you may find there are easier/more efficient approaches

• can find all the documents matching n of the search terms in the phrase, then do exact substring matching in the document
• if search terms have max token length that is relatively short, then you can add n-grams to your search index

This is a very general problem, you can look at implementations in popular search engines like ElasticSearch.