Find a specific value in a large tree of sublists

Question

I have some code that generates a list that looks something like this:

chrs = [[["a",["b","c"]],["d","e"],"f"],["g",[["h","i"],"j"]]]

Now I need to find a specific value in some kind of list like this.
I wrote some code to do this, but it seems to get stuck in an infinite loop:

def locate_value(v,chrs):                       #
    checked=[[]]                                # Set up the values
    index_list=[]                               #
    inside=0                                    #
    cur=[0,0]                                   #
                                                #
    while True:                                 #
        if chrs[cur[0]] == v:                   # If found, end the loop and return the index_list
            return index_list                   #
                                                #
        if type(chrs[cur[0]]) != list:          # If the current is not a list, skip this one
            checked[inside].append(cur[0])      #
            index_list = []                     #
                                                #
        else:                                   #
            try:                                #
                if cur[0] in gone[inside]:      # If the current has been done before, skip it
                    cur[0] += 1                 #
                                                #
                else:                           # And if not, move 1 space deeper
                    checked.append([])          #
                    index_list.append(cur[0])   #
                    cur[1] = cur[0]             #
                    cur[0] = 0                  #
                    inside += 1                 #
                                                #
            except IndexError:                  # And if a sublist is fully checked, block it too
                checked[inside].append(cur[1])  #



print(locate_value("e",[[["a",["b","c"]],["d","e"],"f"],["g",[["h","i"],"j"]]]))

Editing me just realised how bad this code is

In this example, the function locate_value should return [0, 1, 1], as list[0][1][1] is "e"

But when I run this, I get stuck in an infinite loop Can anyone tell me what is wrong, and maybe give me some code that actually works for once.

The list is made with user input, so I have no idea how deep it is.
Though a python-3 only solution is fine, I would prefer one that supports python-2, too.

Does this answer your question? [Finding the index of an element in nested lists in python](https://stackoverflow.com/questions/33938488/finding-the-index-of-an-element-in-nested-lists-in-python) — Bhagyesh Dudhediya, Sep 17 '21 at 09:58
@BhagyeshDudhediya Those seem to work only for lists of lists, not for arbitrary/irregular nesting. — tobias_k, Sep 17 '21 at 10:01
"and maybe give me some code that actually works for once" Oh, I'm sorry, are you not satisfied with our free-of-charge coding support? — tobias_k, Sep 17 '21 at 10:14

score 2 · Answer 1 · answered Sep 17 '21 at 10:00

2

The following will work:

def locate_value(v, chrs):
    if v == chrs:
        return []
    if not isinstance(chrs, list):
        raise IndexError
    for i, c in enumerate(chrs):
        try:
            return [i] + locate_value(v, c)
        except IndexError:
            pass
    raise IndexError


locate_value("e", [[["a",["b","c"]],["d","e"],"f"],["g",[["h","i"],"j"]]])
# [0, 1, 1]

Note that str objects are iterables themselves, so recursively keeping iterating their elements (strings yet again) will never end.

answered Sep 17 '21 at 10:00

user2390182

72,016
6
67
89

Good answer, but the other one was shorter. – TheMystZ Sep 17 '21 at 22:07
It depends on your preferences. Some people prefer simple and readable answers compared to short answers that are difficult to understand. – AloneTogether Jan 07 '22 at 09:51

Corralien · Accepted Answer · 2021-09-17T11:52:55.833

2

Use a recursion function:

def locate_value(v, chrs, idx=[]):
    for j, i in enumerate(chrs):
        if isinstance(i, list):
            yield from find(v, i, idx + [j])
        elif i == v:
            yield idx + [j]

Another version to keep your original signature function:

def locate_value(v, chrs):
    for j, i in enumerate(chrs):
        if isinstance(i, list):
            yield from ([j, *idx] for idx in locate_value(v, i))
        elif i == v:
            yield [j]

Output:

>>> list(locate_value('e', chrs, []))
[[0, 1, 1]]

# case of multiple 'e'
# chrs = [[["a",["b","c"]],["d","e"],"f"],["g",[["h","e"],"j"]]]

>>> list(locate_value('e', chrs))
[[0, 1, 1], [1, 1, 0, 1]]

Greatly improved by @tobias_k

edited Sep 17 '21 at 11:52

answered Sep 17 '21 at 10:03

Corralien

109,409
8
28
52

1

You should change this to `yield from find(...)` and `yield idx + [j]` to make it much more useful, for finding just the `next` or all such index-tuples. – tobias_k Sep 17 '21 at 10:06
@tobias_k. Thanks for this improved code. I am really very grateful to you. – Corralien Sep 17 '21 at 10:21
instead of passing [] as an argument, change `def locate_value(c, chrs, idx):` to `def locate_value(c, chrs, idx=[]):`. This will be more pythonic. – Sep 17 '21 at 10:37
@GoAmeer030. Read https://docs.python-guide.org/writing/gotchas/ – Corralien Sep 17 '21 at 11:31
Alternatively, `idx`-free version, using `yield from ([j, *idx] for idx in find(c, i))` and `yield [j]` respectively. – tobias_k Sep 17 '21 at 11:45
1

I updated my answer with the two solutions. – Corralien Sep 17 '21 at 11:54
Worked! One thing I forgot to mention was that my list also had some tuples in it, but I just adjusted it to look for tuples to. – TheMystZ Sep 17 '21 at 22:06

Find a specific value in a large tree of sublists

2 Answers2