CODEWITHSUNDEEP
pythonalgorithmfunctionloops
duhaime
duhaime

Reputation: 27584

Python: Determine whether list of lists contains a defined sequence

I have a list of sublists, and I want to see if any of the integer values from the first sublist plus one are contained in the second sublist. For all such values, I want to see if that value plus one is contained in the third sublist, and so on, proceeding in this fashion across all sublists. If there is a way of proceeding in this fashion from the first sublist to the last sublist, I wish to return True; otherwise I wish to return False. For each value in the first sublist, I want to see if one can find that value plus n in each sublist reading left to right, where n is the index value of that sublist within the larger list.. (Sorry for the clumsy phrasing--I'm not sure how to clean up my language without using many more words.)

EDIT: (The previous articulation of desired output is ambiguous.) For each value in the first sublist, I want to see if one can find that value plus n in each sublist reading left to right, where n is the index value of that sublist within the larger list.

Here's what I wrote.

a = [ [1,3],[2,4],[3,5],[6],[7] ]

def find_list_traversing_walk(l):

    for i in l[0]:

        index_position = 0
        first_pass = 1
        walking_current_path = 1

        while walking_current_path == 1:

            if first_pass == 1:
                first_pass = 0
                walking_value = i

            if walking_value+1 in l[index_position + 1]:

                index_position += 1
                walking_value  += 1

                if index_position+1 == len(l):
                    print "There is a walk across the sublists for initial value ", walking_value - index_position
                    return True

            else:
                walking_current_path = 0

    return False

print find_list_traversing_walk(a)

My question is: Have I overlooked something simple here, or will this function return True for all true positives and False for all true negatives? Are there easier ways to accomplish the intended task? I would be grateful for any feedback others can offer!

Upvotes: 0

Views: 214

Answers (3)

Warren Weckesser
Warren Weckesser

Reputation: 114781

You can view the desired operation as a reduction on a sequence of sets where the reducing operation is the following function:

In [25]: def func(x, y):
   ....:     return set([t+1 for t in x]) & set(y)
   ....:

That is, func takes two collections, adds 1 to each element in the first collection, and returns the intersection of that and the second collection. Apply this function sequentially across a. If the final result is not an empty set, the answer is True:

In [29]: a = [ [1,3],[2,4],[3,5],[6],[7] ]

In [30]: bool(reduce(func, a))
Out[30]: True

In [31]: b = [ [1],[2,4],[5] ]

In [32]: bool(reduce(func, b))
Out[32]: False

(bool converts a non-empty set to True and an empty set to False.)

Note that if the input is typically a very long sequence, and you expect to know that the answer is False within a few steps, this is not a very efficient solution, since it always traverses the entire input.

Upvotes: 2

wwii
wwii

Reputation: 23743

I also thought it was expressed better recursively. If I understood your problem correctly, this is what I came up with.

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

def foo(data):
    if len(data) == 1:
        return True
    return all(item + 1 in data[1] for item in data[0]) and foo(data[1:])

print foo(a), foo(b), foo(c)
>>> 
False False True
>>>

Upvotes: 0

Nir Alfasi
Nir Alfasi

Reputation: 53525

Are there easier ways to accomplish the intended task?

Yes, it will be easier to define a recursive solution:

def find(lst, index):
    if index == len(lst)-1:
        return True
    for i in lst[index]:
        if i+1 in lst[index+1]:
            return find(lst, index+1)
    else:
        return False             

a = [ [1,3],[2,4],[3,5],[6],[7] ]
print find(a, 0) # prints "True"

a = [ [1,3],[2,4],[3,5],[6],[7], [9] ]
print find(a, 0) # prints "False"

UPDATE
What you describe in your comment is a bit more complex (the need for the next+1 to be one of the "guys" that were used before) - but not much:

def find(lst, part_res, index):
    if index == len(lst)-1:
        return True

    found = False
    new_part_res = []
    for i in part_res:
        if i+1 in lst[index+1]:
            found = True
            new_part_res.append(i+1)

    if not found:
        return False
    else:
        return find(lst, new_part_res, index+1)


a = [ [1,3],[2,4],[3,5],[6],[7] ] 
print find(a, a[0], 0) # True

a = [ [1],[2,4],[5] ]
print find(a, a[0], 0) # False

Upvotes: 2

Related Questions