How to update a list in linear time using its previous index value?

Basically, what I want to do is similar to what the following Python function is doing:

def myfunction(mylist):
    initial = [0]*len(mylist)
    initial[0] = 1
    for i in range(1, len(mylist)):
        initial[i] = mylist[i - 1] * initial[i - 1]

I tried doing something like the code given below, however, it has a complexity more than linear time plus it doesn’t work properly as well since it seems to be using the i value rather than the i-1 value of initial.

def myfunction(mylist) do
	initial = List.duplicate(0, len(mylist))
	initial = List.update_at(initial, 0, &(&1 + 1))

	|> -> 
		initial = List.update_at(initial, i, &(, i-1) * &1))	

Any help would be appreciated over here. Thank you!

Can you explain what the function is actually doing here? What is an example input and output?

1 Like

Using inside of a loop over the length will give you O(N^2) performance. Avoid it at all costs.

In this case, the indexing is mostly superfluous: a value in the output list is a function solely of the current element and the preceding value of the output list.

Since you need all the intermediate values, Enum.scan is a better choice. For instance:

# input list
a = [2, 3, 5]

# prepend a 1
b = [1 | a]

# calculate the running product
Enum.scan(b, 1, &Kernel.*/2)
# returns [1, 2, 6, 30]

So basically, let us say that mylist = [2,3,4,5,6]. Now, initial would be a list of zeros apart from the first index being one, having the following value: [1,0,0,0,0].

Now, the for loop will be running from 1 to the length of mylist which is 5 in this case. Inside this, the initial list is getting updated by multiplying the values of mylist with initial. For example, when i=1, mylist[i-1] would be 2 and initial[i - 1] would be 1 at the start. initial[i] over here would end up becoming 2. Similarly, for i=2, mylist[i-1] would be 3 now, and initial[i - 1] would be 2 and initial[i] over here would end up becoming 6.

Initial would get updated in the following way:

[1, 0, 0, 0, 0]
[1, 2, 0, 0, 0]
[1, 2, 6, 0, 0]
[1, 2, 6, 24, 0]
[1, 2, 6, 24, 120]
1 Like

This is good advice. Thank you. I will check this out.

Yeah I think @al2o3cr 's answer is great. Notice how he frames it in more functional terms, instead of thinking of it as modifying a list at various points. Instead, he’s framing it as generating a new list as a functional mapping over the old list.

So you’re trying to calculate a list of the first n (or rather, the first length(mylist)) factorial numbers?

What about:

defmodule Example do
  def factorial_list(other_list) do
    |> Stream.iterate(fn prev -> prev * prev end)
    |> Enum.take(length(other_list))
1 Like

Won’t this simply give us a list of 1s of length(other_list) if lets say our other_list is [2,3,4,5,6]. And in a way, you’re right about factorial being calculated.

I’m sorry, you’re right.
This is what you’re looking for:

defmodule Example do
  def factorials_list(other_list) do
    Enum.take(factorials(), length(other_list))

  def factorials do
      Stream.scan(positive_integers(), 1, fn index, acc -> index * acc end) 

  def positive_integers do
    Stream.iterate(1, fn prev -> prev + 1 end)
1 Like