This is not the way to do things in Python, but surely - you can traverse a list of lists recursively:
def findList(lst, ele):
if not lst: # base case: the list is empty
return False
elif lst[0] == ele: # check if current element is the one we're looking
return True
elif not isinstance(lst[0], list): # if current element is not a list
return findList(lst[1:], ele)
else: # if current element is a list
return findList(lst[0], ele) or findList(lst[1:], ele)
This is not the way to do things in Python, but surely - you can traverse a list of lists recursively:
def findList(lst, ele):
if not lst: # base case: the list is empty
return False
elif lst[0] == ele: # check if current element is the one we're looking
return True
elif not isinstance(lst[0], list): # if current element is not a list
return findList(lst[1:], ele)
else: # if current element is a list
return findList(lst[0], ele) or findList(lst[1:], ele)
Recursive functions are idiomatic for when you have a linked list. Python lists are more like arrays. But it's still possible to handle a Python list with a recursive function -- there's no real utility, but it can be interesting as an exercise.
You start with a full list, and your base case is when the list is empty. Traverse the list by passing the list in as an argument, using x.pop() to simultaneously fetch and remove the first item in the list, evaluate the popped item, and then pass the list (now shorter) into the same function.
Edit: actually, on second thought, you would be better off not using x.pop() and instead peeking at the first value and passing the remainder in a slice. This would be grossly inefficient, because you're copying the list every time you slice, but it's better than destructively consuming the list inside your recursive function, unless that's a desired side-effect.
python - Iterate a list using recursion - Stack Overflow
python - Recursively iterate over lists - Stack Overflow
python - Iterating through list of list - Stack Overflow
Recursive function to iterate over a list
but I wonder if it's okay there's no "return" line under "else:"
Yes, that's OK. You don't need to return anything from your function if you don't want to. In fact, in the interest of consistency, you may as well remove the thing returned in the if block too:
def printElement(inputlist):
newlist=inputlist
if len(newlist)==0:
return
else:
removedElement=newlist[len(inputlist)-1]
newlist=newlist[:len(inputlist)-1]
Element=printElement(newlist)
print(removedElement)
collection = ['hey', 5, 'd']
printElement(collection)
Is it better code with or without the newlist?
Assigning new things to inputlist won't modify it outside of the function, so there's no harm in doing so. May as well get rid of newlist.
def printElement(inputlist):
if len(inputlist)==0:
return
else:
removedElement=inputlist[len(inputlist)-1]
inputlist=inputlist[:len(inputlist)-1]
Element=printElement(inputlist)
print(removedElement)
collection = ['hey', 5, 'd']
printElement(collection)
you don't use Element after assigning it, so you may as well not assign it at all.
def printElement(inputlist):
if len(inputlist)==0:
return
else:
removedElement=inputlist[len(inputlist)-1]
inputlist=inputlist[:len(inputlist)-1]
printElement(inputlist)
print(removedElement)
collection = ['hey', 5, 'd']
printElement(collection)
You don't really need to modify inputlist, since you only use it once after modifying it. Just stick that expression straight into the printElement call. And now that inputlist is never modified, you can get rid of removedElement too, and just inline its expression in the print function.
def printElement(inputlist):
if len(inputlist)==0:
return
else:
printElement(inputlist[:len(inputlist)-1])
print(inputlist[len(inputlist)-1])
collection = ['hey', 5, 'd']
printElement(collection)
Fun fact: for any list x, x[len(x)-1] can be shortened to x[-1]. Same with x[:len(x)-1] to x[:-1].
def printElement(inputlist):
if len(inputlist)==0:
return
else:
printElement(inputlist[:-1])
print(inputlist[-1])
collection = ['hey', 5, 'd']
printElement(collection)
Since the first block unconditionally returns, you could remove the else and just put that code at the function level, without changing the code's behavior. Some people find this less easy to read. Personally, I like my code to have the least amount of indentation possible.
def printElement(inputlist):
if len(inputlist)==0:
return
printElement(inputlist[:-1])
print(inputlist[-1])
collection = ['hey', 5, 'd']
printElement(collection)
That's about as compact as you can get, with a recursive solution. You should probably just stick with the iterative version, for a few reasons:
- Fewer lines
- More easily understood
- Doesn't raise a "maximum recursion depth exceeded" exception on lists with 200+ elements
Your function is needlessly complicated. The return value is never used. You also print from the end of the list, which is a bit odd: tail recursion is a more usual style. For example:
def printCollection(c):
if c:
print c[0]
printCollection(c[1:])
This still has the flaw that it copies the list for every element in the list, making it an O(n^2) function. It's also limited to data structures that use slices and indices. Here's a recursive version that prints any iterable:
def printCollection(c):
it = iter(c)
try:
el = it.next()
print el
printCollection(it)
except StopIteration:
pass
It's still a bit odd to recurse here as this is a naturally iterative problem.
It looks like you've made every step slightly more complicated than necessary. I believe this generates the information you desire:
import json
FILE = "somefile.json"
def find_path(test_name, data):
dictionary = return_test_data(test_name, data)
if dictionary:
current_steps = [test_name]
if 'parents' in dictionary:
for parent in dictionary['parents']:
current_steps.extend(find_path(parent, data))
return current_steps
return None
def return_test_data(name, data):
for dictionary in data['cases']:
if dictionary['name'] == name:
return dictionary
return None
if __name__ == "__main__":
data = json.load(open(FILE))
steps = find_path("A", data)
print("Steps:", steps)
OUTPUT
> python3 test.py
Steps: ['A', 'E', 'B', 'C', 'E', 'D', 'E']
>
You can iterate on the structure like this:
Code:
parents_list = []
for record in data:
if record['name'] not in parents_list:
parents_list.append(record['name'])
for p in record['parents']:
parents_list.append(p)
print(parents_list)
Results:
['A', 'E', 'B', 'C', 'E', 'D', 'E']
This traverse generator function can be used to iterate over all the values:
def traverse(o, tree_types=(list, tuple)):
if isinstance(o, tree_types):
for value in o:
for subvalue in traverse(value, tree_types):
yield subvalue
else:
yield o
data = [(1,1,(1,1,(1,"1"))),(1,1,1),(1,),1,(1,(1,("1",)))]
print list(traverse(data))
# prints [1, 1, 1, 1, 1, '1', 1, 1, 1, 1, 1, 1, 1, '1']
for value in traverse(data):
print repr(value)
# prints
# 1
# 1
# 1
# 1
# 1
# '1'
# 1
# 1
# 1
# 1
# 1
# 1
# 1
# '1'
So wait, this is just a list-within-a-list?
The easiest way is probably just to use nested for loops:
>>> a = [[1, 3, 4], [2, 4, 4], [3, 4, 5]]
>>> a
[[1, 3, 4], [2, 4, 4], [3, 4, 5]]
>>> for list in a:
... for number in list:
... print number
...
1
3
4
2
4
4
3
4
5
Or is it something more complicated than that? Arbitrary nesting or something? Let us know if there's something else as well.
Also, for performance reasons, you might want to look at using list comprehensions to do this:
http://docs.python.org/tutorial/datastructures.html#nested-list-comprehensions
I'm pretty new to programming and still feel a bit shaky when it comes to recursive functions. I was reviewing some documentation on lists and saw that len() will only count "top level" items in a list, i.e. if your list contains a dict or another list, it won't count the number of items in the nested list or dict.
I thought it might be fun (and good practice) to try writing a function that will count every item, no matter how nested it was. I realized quickly that I should try using recursion, and after some fiddling around I made something that works!
I know it's not groundbreaking but I'm proud of the progress I'm making and just wanted to share.
def listcounter(x):
counter = 0
for i in x:
if type(i) == list or type(i)==dict:
counter = counter + listcounter(i)
else:
counter = counter + 1
return counter
If you are starting with two lists and want to compare them element-wise you can use zip() to simplify your life. It will give you back the elements paired off. So if you are starting with two lists, you can zip them:
list1 = ['A', 'T']
list2 = ['C', 'G']
zipped = list(zip(list1, list2))
# zipped is [('A', 'C'), ('T', 'G')]
#or use a list comprehension:
zipped = [pair for pair in zip(list1, list2)]
zip() returns an iterator which is why it's wrapped in list() above. If you use it in a loop or other situation calling for a interator, you don't need to do that.
If you want to compare these you can use a dictionary that defines which letter maps to the other, this will allow you write a much simpler test function:
# Define a mapping that describes which elements belong togethre
pairs = {
'G':'T',
'T':'G',
'C':'A',
'A':'C'
}
list1 = ['A', 'A', 'T', 'C', 'G', 'C', 'T', 'A']
list2 = ['C', 'G', 'G', 'A', 'C', 'A', 'C', 'T']
# make a new list if the pairs line up with the mapping:
legal = [(a, b) for a, b in zip(list1, list2) if pairs[a] == b ]
# legal pairs: [('A', 'C'), ('T', 'G'), ('C', 'A'), ('C', 'A')]
There's not much reason to do this recursively, but you of course can. Since zip() returns an iterator (pairs below) you can call next() on it to get there next value and then pass the iterator back. It will throw a StopIteration error when it's out of items, so that can be the edge condition of the recursion:
def buildList(pairs, mapping):
''' Takes an iterator and mapping, returns a list of legal items defined by mapping '''
try:
a_pair = next(pairs) # get first item from zipped list
except StopIteration: # no more items, just return an empty list
return []
a, b = a_pair
if mapping[a] == b:
return [(a, b)] + buildList(pairs, mapping)
else:
return buildList(pairs, mapping)
list1 = ['A', 'A', 'T', 'C', 'G', 'C', 'T', 'A']
list2 = ['C', 'G', 'G', 'A', 'C', 'A', 'C', 'T']
pairs = {'G':'T','T':'G','C':'A','A':'C'}
buildList(zip(list1, list2), pairs) # use zip to make the zipped iterator
This question is tagged with recursion and here's my take on it -
def head(xs = []):
return xs[0]
def tail(xs = []):
return xs[1:]
def check_pair(x = "", y = "", swap = True):
if x == "A" and y == "C":
return True
elif x == "G" and y == "T":
return True
else:
return swap and check_pair(y, x, False)
def check_valid(a = [], b = []):
if (not a) or (not b):
return
elif check_pair(head(a), head(b)):
yield (head(a), head(b))
yield from check_valid(tail(a), tail(b))
else:
yield from check_valid(tail(a), tail(b))
a = ['A', 'A', 'T', 'C', 'G', 'C', 'T', 'A']
b = ['C', 'G', 'G', 'A', 'C', 'A', 'C', 'T']
print(list(check_valid(a,b)))
# [('A', 'C'), ('T', 'G'), ('C', 'A'), ('C', 'A')]
This is intuitive, but like zip, the tail function creates intermediate values. We can reduce memory requirement by using a simple index, i -
def check_pair(x = "", y = "", swap = True):
if x == "A" and y == "C":
return True
elif x == "G" and y == "T":
return True
else:
return swap and check_pair(y, x, False)
def check_valid(a = [], b = [], i = 0):
if i >= min(len(a), len(b)):
return
elif check_pair(a[i], b[i]):
yield (a[i], b[i])
yield from check_valid(a, b, i + 1)
else:
yield from check_valid(a, b, i + 1)
a = ['A', 'A', 'T', 'C', 'G', 'C', 'T', 'A']
b = ['C', 'G', 'G', 'A', 'C', 'A', 'C', 'T']
print(list(check_valid(a,b)))
# [('A', 'C'), ('T', 'G'), ('C', 'A'), ('C', 'A')]
You may be interested in this related Q&A
I have this exercise I am tring online which take a bunch of lists and zip them together. first and then returns a list. For example, the input func([1,2,3], [20,30,40], ['a', 'b', 'c']) should return [1, 20, 'a', 2, 30, 'b', 3, 40, 'c']
However I do not know how to iterate over the list. I don't even know if it's possible. I tried
def func(*args):
for n in args:
ans = list(zip(n))
return ans
But I just get : [(1,), (2,), (3,)]
you can use python's really cool slicing syntax:
new_list=my_list[::2]
to get every other element.
It means new_list is my_list from the begining to the end with a stride of 2
then your ramainder elements are elements_not_used = [item for item in my_list if item not in new_list] and you can just continue until len(my_list)<2
Yes, you can use a while loop with a generator:
L = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
def recursive_odds(x):
while x:
yield from x[::2]
x = x[1::2]
res = list(recursive_odds(L))
[2, 6, 10, 14, 18, 4, 12, 20, 8, 16]
Hey all,
Was reading through a Python textbook and the author posted a problem about taking a list that potentially is very deeply nested (e.g. [[[[[[[[[[[[[[[[[[[[[[[1,3,4,5],[4]....) and writing a script to sum up all those numbers (I don’t believe built-in sum works on nested lists). I made the problem a bit more general — how do you take an arbitrarily nested list and strip out all the extra structure to get a list of minimal depth? (E.g., the above would be [1,3,4,5,4...]
I came up with this.
def structureSlayer(L): L2 = [] for item in L: try: L2.extend(structureSlayer(item)) except: L2.append(item) return L2
idea is that it gets top-level elements of a list, then tries to iterate over those elements (which works if they’re lists themselves). It spits out an error it tries to loop over a single element, like “4” in the above list, which is caught by except and taken out of the nested for loop function calls. Essentially each call to structureSlayer reduces the depth (if possible) of all list elements by 1.
I glanced at the sample code after I did the above, and the author has an explicit type test (testing if each
itemis alisttype, then going deeper into the recursion). Aren’t type tests frowned upon in Python? It didn’t seem to simplify the code at all and maybe costs some flexibility?This code also works if there’s, say, a string somewhere in my list, and I don’t fully understand why. Eventually (after nesting some amount of for loops with repeated
structureSlayercalls, it seems likeitemis going to hit a string, split it into single-character strings, and then loop endlessly over those (a single-character string is still iterable?) Why does the loop terminate ifL = [1,[2,’hey’]], for instance?