CODEWITHSUNDEEP
listfunctional-programmingerlangruntime
GTDev
GTDev

Reputation: 5528

Erlang Iterating through list removing one element

I have the following erlang code:

lists:all(fun(Element) -> somefunction(TestCase -- [Element]) end, TestCase).

Where TestCase is an array. I'm trying to iterate over the list/array with one element missing.

The problem is this code takes O(N^2) time worst case because of the copies of the TestCase array everytime -- is called. There is a clear O(N) Solution in a non functional language.

saved = TestCase[0]
temp = 0
NewTestCase = TestCase[1:] 
for a in range(length(NewTestCase)):
  somefunction(NewTestCase)
  temp = NewTestCase[a]
  NewTestCase[a] = saved
  saved = temp

... or something like that.

Is there an O(N) solution in erlang?

Upvotes: 0

Views: 1864

Answers (2)

aronisstav
aronisstav

Reputation: 7994

Of course there is, but it's a little bit more complicated. I am assuming that some_function/1 is indeed a boolean function and you want to test whether it returns true for every sub-list.

test_on_all_but_one([], _Acc) -> true;
test_on_all_but_one([E|Rest], Acc) ->
  case somefunction(lists:reverse(Acc,Rest)) of
    true  -> test_on_all_but_one(Rest, [E|Acc]);
    false -> false
  end.

This implementation is still O(length(List)^2) as the lists:reverse/2 call will still need O(length(Acc)). If you can modify somefunction/1 to do it's calculation on a list split into two parts, then you can modify the previous call to somefunction(lists:reverse(Acc,Rest)) with somefunction(Acc, Rest) or something similar and avoid the reconstruction.

The modification depends on the inner workings of somefunction/1. If you want more help with that, give some code!

Upvotes: 1

alvelcom
alvelcom

Reputation: 408

You can split the list into 2 sublists, if it's acceptable of course.

witerate(Fun, [Tail], Acc) ->
  Fun([], Acc);

witerate(Fun, [Head | Tail], Acc) ->
  Fun(Tail, Acc),
  witerate(Fun, Tail, [Head | Acc]).

Upvotes: 0

Related Questions