Re: [Tutor] Recursively flatten the list
On 01/-10/-28163 02:59 PM, Prasad, Ramit wrote:" >A more important problem is that it is flattening only one level. >Multi-level flattening is I think not possible without using some kind >of recursion." > >Not true, just requires more iterations to check each element. Each >iteration could check if every element is a list and then unpack if it >is a list. When you finally have an iteration that has no lists, you >can end the loop. > >Not time efficient or pretty but it would certainly work without >recursion. I am sure people on this list can provide a better answer >than I can :) > > >Ramit Indeed, something like the following would suffice, in one "pass". Untested: index = 0 while index < len(mylist): if isinstance(mylist[index), list): mylist[index:index+1] = mylist[index] else index += 1 DaveA ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Recursively flatten the list
" A more important problem is that it is flattening only one level. Multi-level flattening is I think not possible without using some kind of recursion." Not true, just requires more iterations to check each element. Each iteration could check if every element is a list and then unpack if it is a list. When you finally have an iteration that has no lists, you can end the loop. Not time efficient or pretty but it would certainly work without recursion. I am sure people on this list can provide a better answer than I can :) Ramit Ramit Prasad | JPMorgan Chase Investment Bank | Currencies Technology 712 Main Street | Houston, TX 77002 work phone: 713 - 216 - 5423 This communication is for informational purposes only. It is not intended as an offer or solicitation for the purchase or sale of any financial instrument or as an official confirmation of any transaction. All market prices, data and other information are not warranted as to completeness or accuracy and are subject to change without notice. Any comments or statements made herein do not necessarily reflect those of JPMorgan Chase & Co., its subsidiaries and affiliates. This transmission may contain information that is privileged, confidential, legally privileged, and/or exempt from disclosure under applicable law. If you are not the intended recipient, you are hereby notified that any disclosure, copying, distribution, or use of the information contained herein (including any reliance thereon) is STRICTLY PROHIBITED. Although this transmission and any attachments are believed to be free of any virus or other defect that might affect any computer system into which it is received and opened, it is the responsibility of the recipient to ensure that it is virus free and no responsibility is accepted by JPMorgan Chase & Co., its subsidiaries and affiliates, as applicable, for any loss or damage arising in any way from its use. If you received this transmission in error, please immediately contact the sender and destroy the material in its entirety, whether in electronic or hard copy format. Thank you. Please refer to http://www.jpmorgan.com/pages/disclosures for disclosures relating to European legal entities. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Recursively flatten the list
2011/3/24 Rafael Durán Castañeda : > I can do it with two list comprehensions: > list_ = [1, 2, [3, 4], 5, [6, 7, 8], 9] [x[i] for x in list_ if isinstance(x, list) for i in range(len(x))] + [x for x in list_ if not isinstance(x, list)] > [3, 4, 6, 7, 8, 1, 2, 5, 9] > > But i loose original order, Can anyone do it with just one list > comprehension and/or keeping the order? A more important problem is that it is flattening only one level. Multi-level flattening is I think not possible without using some kind of recursion. -- André Engels, andreeng...@gmail.com ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Recursively flatten the list
I can do it with two list comprehensions: >>> list_ = [1, 2, [3, 4], 5, [6, 7, 8], 9] >>> [x[i] for x in list_ if isinstance(x, list) for i in range(len(x))] + [x for x in list_ if not isinstance(x, list)] [3, 4, 6, 7, 8, 1, 2, 5, 9] >>> But i loose original order, Can anyone do it with just one list comprehension and/or keeping the order? I also tryied: >>> [x if not isinstance(x, list) else (x[i] for i in range(len(x))) for x in list_] [1, 2, at 0x187f7d0>, 5, at 0x187f870>, 9] >>> [x if not isinstance(x, list) else [x[i] for i in range(len(x))] for x in list_] [1, 2, [3, 4], 5, [6, 7, 8], 9] >>> 2011/3/24 Tom Zych > Dharmit Shah wrote: > > I am learning Python and yesterday I cam across a definition wherein I > was > > supposed to flatten a list recursively. I am getting the solution > properly > > but wanted to know if I can optimize the code further. > > > > #!/usr/bin/env python > > new_list=[] > > def flatten(num_list): > > """ > > >>> flatten([2, 9, [2, 1, 13, 2], 8, [2, 6]]) > > [2, 9, 2, 1, 13, 2, 8, 2, 6] > > >>> flatten([[9, [7, 1, 13, 2], 8], [7, 6]]) > > [9, 7, 1, 13, 2, 8, 7, 6] > > >>> flatten([[9, [7, 1, 13, 2], 8], [2, 6]]) > > [9, 7, 1, 13, 2, 8, 2, 6] > > >>> flatten([[5, [5, [1, 5], 5], 5], [5, 6]]) > > [5, 5, 1, 5, 5, 5, 5, 6] > > """ > > global new_list > > for i in num_list: > > if type(i) == type([]): > > new_list = flatten(i) > > else: > > new_list.append(i) > > tmp = new_list > > new_list=[] > > return tmp > > > > if __name__=="__main__": > > import doctest > > doctest.testmod() > > > > PS - My knowledge of Python is still very basic and I am trying to dive > into > > it as deeper as I can. Solutions on Stackoverflow.com were beyond my > > understandability. > > Using doctest and getting a recursive function right don't strike me as > basic. This is pretty good for a beginner. > > I'll second Peter Otten regarding the use of a global. It's best to > avoid using globals whenever possible, not just for reentrancy, but for > more readable and maintainable code. A function should be self-contained > if possible. There's no reason you can't use a local variable in this > code (and you only need one, not two), and the resulting code would be > more readable. > > Regarding this line: >if type(i) == type([]): > > This also works: >if type(i) == list: > > But this is better: >if isinstance(i, list): > > isinstance(obj, class) means "is obj an instance of class or a subtype > of class", so it's more general. > > Does anyone see a way to do this with a list comprehension? I don't. > Would be a neat hack if it can be done. > > -- > Tom Zych / freethin...@pobox.com > "Because if they didn't vote for a lizard," said Ford, "the wrong lizard > might get in." -- DNA > > ___ > Tutor maillist - Tutor@python.org > To unsubscribe or change subscription options: > http://mail.python.org/mailman/listinfo/tutor > ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Recursively flatten the list
Dharmit Shah wrote: > I am learning Python and yesterday I cam across a definition wherein I was > supposed to flatten a list recursively. I am getting the solution properly > but wanted to know if I can optimize the code further. > > #!/usr/bin/env python > new_list=[] > def flatten(num_list): > """ > >>> flatten([2, 9, [2, 1, 13, 2], 8, [2, 6]]) > [2, 9, 2, 1, 13, 2, 8, 2, 6] > >>> flatten([[9, [7, 1, 13, 2], 8], [7, 6]]) > [9, 7, 1, 13, 2, 8, 7, 6] > >>> flatten([[9, [7, 1, 13, 2], 8], [2, 6]]) > [9, 7, 1, 13, 2, 8, 2, 6] > >>> flatten([[5, [5, [1, 5], 5], 5], [5, 6]]) > [5, 5, 1, 5, 5, 5, 5, 6] > """ > global new_list > for i in num_list: > if type(i) == type([]): > new_list = flatten(i) > else: > new_list.append(i) > tmp = new_list > new_list=[] > return tmp > > if __name__=="__main__": > import doctest > doctest.testmod() > > PS - My knowledge of Python is still very basic and I am trying to dive into > it as deeper as I can. Solutions on Stackoverflow.com were beyond my > understandability. Using doctest and getting a recursive function right don't strike me as basic. This is pretty good for a beginner. I'll second Peter Otten regarding the use of a global. It's best to avoid using globals whenever possible, not just for reentrancy, but for more readable and maintainable code. A function should be self-contained if possible. There's no reason you can't use a local variable in this code (and you only need one, not two), and the resulting code would be more readable. Regarding this line: if type(i) == type([]): This also works: if type(i) == list: But this is better: if isinstance(i, list): isinstance(obj, class) means "is obj an instance of class or a subtype of class", so it's more general. Does anyone see a way to do this with a list comprehension? I don't. Would be a neat hack if it can be done. -- Tom Zych / freethin...@pobox.com "Because if they didn't vote for a lizard," said Ford, "the wrong lizard might get in." -- DNA ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Recursively flatten the list
Dharmit Shah wrote: > I am learning Python and yesterday I cam across a definition wherein I was > supposed to flatten a list recursively. I am getting the solution properly > but wanted to know if I can optimize the code further. > > #!/usr/bin/env python > new_list=[] > def flatten(num_list): > """ > >>> flatten([2, 9, [2, 1, 13, 2], 8, [2, 6]]) > [2, 9, 2, 1, 13, 2, 8, 2, 6] > >>> flatten([[9, [7, 1, 13, 2], 8], [7, 6]]) > [9, 7, 1, 13, 2, 8, 7, 6] > >>> flatten([[9, [7, 1, 13, 2], 8], [2, 6]]) > [9, 7, 1, 13, 2, 8, 2, 6] > >>> flatten([[5, [5, [1, 5], 5], 5], [5, 6]]) > [5, 5, 1, 5, 5, 5, 5, 6] > """ > global new_list > for i in num_list: > if type(i) == type([]): > new_list = flatten(i) > else: > new_list.append(i) > tmp = new_list > new_list=[] > return tmp > > if __name__=="__main__": > import doctest > doctest.testmod() > > PS - My knowledge of Python is still very basic and I am trying to dive > into it as deeper as I can. Solutions on Stackoverflow.com were beyond my > understandability. You have a working solution, and you have tests to prove it. That's a good start! Now let's think more tests to break it: (1) Deeply nested lists: items = [] for i in range(2000): items = [items] flatten(items) Python has a limited stacksize, i. e. allows only for a limited number of nested function calls. There's not much you can do about that other than switch to a non-recursive implementation of flatten(). Most of the time it's not a problem in practice; you should just know about it. (2) Lists that contain themselves: items = [] items.append(items) flatten(items) This one would run forever were it not for the limited stack size. You are even less likely to run into that in practice, but it might still be an interesting challenge for you to come up with a solution for the problem. (3) Multithreaded programs: Because you use a global variable you cannot run two instances of the function simultaneously. This problem leads to intermittent bugs that are really hard to find. You should try to eliminate the global new_list variable from your flatten() function. Unfortunately the demo is a bit messy, so don't waste too much time on trying to understand it. You can revisit it later if you like. Just remember the rule of thumb: don't use global variables if you can avoid them. if __name__=="__main__": import threading def set_flattened(num_list, index): results[index] = flatten(num_list) A = [5, [5, [1, 5], 5], 5], [5, 6] B = [[50, [50, [10, 50], 50], 50], [50, 60]] EXPECTED = [flatten(A), flatten(B)] print "expected output:" print EXPECTED i = 1 results = [None, None] while True: # run flatten() in two threads simultaneously... a = threading.Thread(target=set_flattened, args=(A, 0)) b = threading.Thread(target=set_flattened, args=(B, 1)) for t in a, b: t.start() for t in a, b: t.join() #... until we see an unexpected result if results != EXPECTED: print "The %dth attempt gave this preculiar result:" % i print results break i += 1 ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
[Tutor] Recursively flatten the list
Hello, I am learning Python and yesterday I cam across a definition wherein I was supposed to flatten a list recursively. I am getting the solution properly but wanted to know if I can optimize the code further. #!/usr/bin/env python new_list=[] def flatten(num_list): """ >>> flatten([2, 9, [2, 1, 13, 2], 8, [2, 6]]) [2, 9, 2, 1, 13, 2, 8, 2, 6] >>> flatten([[9, [7, 1, 13, 2], 8], [7, 6]]) [9, 7, 1, 13, 2, 8, 7, 6] >>> flatten([[9, [7, 1, 13, 2], 8], [2, 6]]) [9, 7, 1, 13, 2, 8, 2, 6] >>> flatten([[5, [5, [1, 5], 5], 5], [5, 6]]) [5, 5, 1, 5, 5, 5, 5, 6] """ global new_list for i in num_list: if type(i) == type([]): new_list = flatten(i) else: new_list.append(i) tmp = new_list new_list=[] return tmp if __name__=="__main__": import doctest doctest.testmod() PS - My knowledge of Python is still very basic and I am trying to dive into it as deeper as I can. Solutions on Stackoverflow.com were beyond my understandability. -- Regards Dharmit Shah ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor