CODEWITHSUNDEEP
pythonrecursionnested-lists
azyeboo
azyeboo

Reputation: 13

How to recursively collect linked information in nested list on Python?

i am a beginner on python and I have a problematic situation that I don't know how to handle.

I have a nested list which have a string and a tuple of three string for each sublist:

[['V1', ('P1', 'B', 'X')], ['R1', ('S1', 'B', 'G')], ['V1', ('R1', 'B', 'L')], ['R1', ('Z1', 'B', 'Z')], ['R1', ('P1', 'X', 'A')], ['P1', ('R1', 'X', 'B')]]

And I need to track common information from key to key to get a stimulation chain.

For exemple in the first sublist which belongs to 'V1' we have 'P1' in first position and 'X' in third the position of the tuple. That means we have already a link between V1 and P1. But for being able to track even further i need to search a sublist which have 'P1' as first element and 'X' in its tuple on second position, for exemple something like the last exemple of list:

['P1', ('R1', 'X', 'B')]]

If that connection exist that means that we have a chain between V1 -> P1 -> R1

And i should continue with 'R1' as next first position of a sublist and 'B' as the second condition in its tuple. For exemple:

['R1', ('Z1', 'B', 'Z')]

And this modifies our chain as V1 -> P1 -> R1 ->Z1

This recursion should continue until we don't get to find our first element of sublist with the condition on second position of its tuple.

I should precise that if there is more than one possibility of connection those possibilities should form different chains like:

V1 -> P1 -> R1 ->Z1
V1 -> P1 -> R1 ->S1

I already tried to write a recursive function for tracking all linked data but it didn't quite work like how it should be.

def loop_search(item, listt):
    list_rel=[item[0]] #we will save chain in form of a list
    if len(listt)==0:
        return list_rel
    else:
        for i in listt:
            if item[1][0]==i[0] and item[1][2]==i[1][1]:
                list_rel.append(loop_search(i,listt[len(listt):]))

Thank you in advance for your help.

Upvotes: 0

Views: 194

Answers (1)

cdlane
cdlane

Reputation: 41905

I believe you've seriously underestimated the amount of logic necessary to implement what you describe. If there is more than one possibility, then at each level you need to deal with all the possibilities being returned from the recursion, your code is only thinking singletons. And other issues:

LINKS = [ \
    ['V1', ('P1', 'B', 'X')], \
    ['R1', ('S1', 'B', 'G')], \
    ['V1', ('R1', 'B', 'L')], \
    ['R1', ('Z1', 'B', 'Z')], \
    ['R1', ('P1', 'X', 'A')], \
    ['P1', ('R1', 'X', 'B')], \
]

def link_search_recursive(item, links):
    _, (first, _, effect) = item

    chains = []

    for idx, link in enumerate(links):

        link_key, (link_first, cause, _) = link

        if first == link_key and effect == cause:

            sub_chains = link_search_recursive(link, links[:idx] + links[idx + 1:])

            if sub_chains:
                for chain in sub_chains:
                    chains.append([first] + chain)
            else:
                chains.append([first, link_first])

    return chains

def link_search(item, links):
    chains = link_search_recursive(item, links)

    key, _ = item

    return [[key] + chain for chain in chains]

print(link_search(LINKS[0], LINKS[1:]))
print(link_search(LINKS[-1], LINKS[:-1]))

You need to carefully describe each structure along the way and account for everything.

OUTPUT

> python3 test.py
[['V1', 'P1', 'R1', 'S1'], ['V1', 'P1', 'R1', 'Z1']]
[['P1', 'R1', 'S1'], ['P1', 'R1', 'Z1']]
>

Upvotes: 1

Related Questions