Most pythonic way to iteratively create a list?

Question

I tried to do something in Python that uses the following general procedure, and I want to know how best to accomplish this.

First, the initialization step:

• Create item M.
• Create a list L and add M to L.

Secondly, do the following:

• Create a new item by changing the last item added to L.
• Add a new item to L.

As a simple example, let's say I want to create a list of lists, where the nth list contains numbers from 1 to n. I could use the following (stupid) procedure.

• Initially, M is [1] and L = [[1]].
• Then change [1] by adding 2 to it to create a new element [1,2], then add [1,2] to L so that L = [[1], [1,2]].
• Then change [1,2] by adding 3 to it to create a new element [1,2,3], then add [1,2,3] to L so that L = [[1], [1, 2] , [1,2,3]].
• Then modify [1,2,3] by adding 4 to it to create a new element [1,2,3,4], then add [1,2,3,4] to L so that L = [[1] , [1,2], [1,2,3], [1,2,3,4]]. and etc.

I tried a few things, but most of them would change not only the last element added, but also the elements added to L in the previous steps. For a specific problem that I was interested in, I managed to find a solution that behaves correctly (at least for small cases), but seems inelegant, I'm not sure why it works when other things haven’t been done, and I don’t even I am sure that this will continue to behave at will for large occasions. I am also not sure that I can adapt my approach to such problems. This is not the case when I do not understand the problem, because without any problems I encoded the same thing in other programming languages.

So, I wonder how more experienced Python programmers will handle this common task.

(Im omitting my own code in part because Im new here and I havent figured out how to enter it in stackoverflow, but also because it is long-ish and I don't need help with a specific problem, but rather with how refer to the more general procedure described above).

Answer 1

When you add an object of list M to another list, you add a link ; continuing to manipulate the list M means that you will see these changes reflected in other links:

 >>> M = [] >>> resultlist = [] >>> resultlist.append(M) >>> M is resultlist[0] True >>> M.append(1) >>> resultlist[0] [1] >>> M [1] 

Note that M is resultlist[0] - True; this is the same object.

Instead, you should add a copy of M :

 resultlist.append(M[:]) 

The whole fragment here ( [:] means slice from start to finish) creates a new list with a shallow copy of the contents of M

A general way of constructing a series L from a continuously modified starting point M is to use the generator function. Simply adding the following number to M can be implemented as:

 def growing_sequence(): M = [] counter = 0 while True: M.append(counter) counter += 1 yield M[:] 

This will result in longer lists every time you repeat the query:

 >>> gen = growing_sequence() >>> next(gen) [0] >>> next(gen) [0, 1] >>> for i, lst in enumerate(gen): ... print i, lst ... if i == 2: break ... 0 [0, 1, 2] 1 [0, 1, 2, 3] 2 [0, 1, 2, 3, 4] 

Answer 2

It will be based on iterate from Haskell.

iterate :: (a -> a) -> a -> [a]

iterate fx returns an endless list of repeating applications f - x :

iterate fx == [x, fx, f (fx), ...]

In Python:

 def iterate(f, x): while True: yield x x = f(x) 

Usage example:

 >>> import itertools.islice >>> def take(n, iterable): ... return list(islice(iterable, n)) >>> take(4, iterate(lambda x: x + [len(x) + 1], [1])) [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]] 

---

To create an end list, a type signature (starting again in Haskell for clarity only) can be infiniteFinitely :: (a -> Maybe a) -> a -> [a] .

If we used list instead of Maybe in Python:

 from itertools import takewhile def iterateFinitely(f, x): return map(lambda a: a[0], takewhile(len, iterate(lambda y: f(y[0]), [x]))) 

Usage example:

 >>> list(iterateFinitely(lambda x: [x / 2] if x else [], 20)) [20, 10, 5, 2, 1, 0] 

---

Since ending with a fake value is probably pretty common, you can also add a version of this function that does this.

 def iterateUntilFalsy(f, x): return iterateFinitely(lambda y: [f(y)] if y else [], x) 

Usage example:

 >>> list(iterateUntilFalsy(lambda x: x / 2, 20)) [20, 10, 5, 2, 1, 0] >>> list(iterateUntilFalsy(lambda x: x[1:], [1,2,3,4])) [[1, 2, 3, 4], [2, 3, 4], [3, 4], [4], []] 

Answer 3

You can do:

 M=[1] L=[M] for e in range(5): li=L[-1][:] li.append(li[-1]+1) L.append(li) 

Or more briefly:

 for e in range(5): L.append(L[-1][:]+[L[-1][-1]+1]) 

Answer 4

I think the best way to do this is with a generator . Thus, you do not need to deal with list.append , deep copy lists or any of these nonsense.

 def my_generator(max): for n in range(max+1): yield list(range(n+1)) 

Then you just need to specify: if / it>

 >>> list(my_generator(5)) [[0], [0,1], [0,1,2], [0,1,2,3], [0,1,2,3,4], [0,1,2,3,4,5]] 

This approach is also more flexible if you want to make it an infinite generator. Just switch the for while true to while true .

Answer 5

Try the following:

 M = [1] L = [M] for _ in xrange(3): L += [L[-1] + [L[-1][-1] + 1]] 

After executing the above code, L will contain [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]] . Explanation:

• The first two lines just seed the iteration with the initial values
• The for line indicates how many cycles we want to execute after the initial value has been set, 3 in this case. I use _ as an iteration variable, because we are not interested in its value, we just want to make a certain number of loops

Now for the interesting part; and remember that in Python a negative index in a list starts from the end, so an index of -1 indicates the last element.

• This: L += … updates the list by adding a new sublist at the end as many times as indicated in the loop
• This: [L[-1] + …] creates a new sublist, taking the last sublist and adding a new item at the end
• And finally, this: [L[-1][-1] + 1] gets the previous last element in the last sublist, adds it to it and returns one element list that will be concatenated at the end of the previous expression