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

Questions / Help
1

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))

	1..len(mylist)-1
	|> Enum.map(fn(i) -> 
		initial = List.update_at(initial, i, &(Enum.at(mylist, i-1) * &1))	
		initial					
	end)
end

Any help would be appreciated over here. Thank you!

2

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

1 Like
3

Using Enum.at 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]
3 Likes
4

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
5

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

6

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.

7

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
    1  
    |> Stream.iterate(fn prev -> prev * prev end)
    |> Enum.take(length(other_list))
  end
end
1 Like
8

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.

10

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))
  end

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

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