Iterating a list to compare all elements with each other

Questions / Help
,
#1

In imperative languages, if one wants to compare every element in an array with the other they can use nested loops where the inner loop starts from the iterator of the outer loop. This avoids comparing elements with each other twice.

E.g.

int best = 0
for (int i = 0; i < a.length; i++) {
    for (int k = i + 1; k < a.length; k++) {
            best = max(best, compare(a[i], a[k]))
    }
}

In Elixir, say I wanted to compare every value in a list with the others and find the best score (according to some arbritrary comparison) I could do something like

Enum.reduce(big_list_of_things, 0, fn
  a, best ->
    max(
      best,
      Enum.reduce(big_list_of_things, fn b, inner_best -> max(inner_best, compare(a, b)) end)
    )
end)

This works, but involves iterating more times than needed (On^2). How might one refactor this so the inner iteration only reduces over what’s left?

#2

You are trying to find the max from a list?

Below code achieves the same thing

[first | rest] = big_list_of_things
Enum.reduce(rest, first, fn x, acc ->
  case x > acc do
    true ->
      x
    false ->
      acc
  end
end)

Enum.max/2 and Enum.max_by/4 can do the same.

Edit: Sorry, I got it all wrong.

The problem here is about finding best score from all combinations of 2 items in list (nc2) - @LostKobrakai’s Post -#3 and Post 4 are generating these combinations of 2.

#3

You can do the same with recursion:

list = [1, 2, 3, 4]

defmodule Rec do
  def compare(list, acc \\ [])

  def compare([_], acc) do
    acc
    |> Enum.reverse()
    |> List.flatten()
  end

  def compare([cur | rest], acc) do
    compare(rest, [Enum.map(rest, &{cur, &1}) | acc])
  end
end

Rec.compare(list)
# [{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}]

And you can look at combinatorics: GitHub - tallakt/comb: Elixir combinatorics - permutations and combinations of lists

6 Likes
#4

Another option are streams:

list = [1, 2, 3, 4]

stream = 
  Stream.transform(list, list, fn _, [cur | rest] -> 
    {Enum.map(rest, &{cur, &1}), rest}
  end)

Enum.into(stream, [])
# [{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}]
5 Likes
#5

That is beautiful.

2 Likes
#6

A for comprehension with two generators from the same source list and a filter can do the job

for x <- list, y <- list, x < y, reduce: 0, do: (best -> max(best, compare(x, y))
4 Likes
#7

Probably not optimal, but by the look of it I would do:
list |> List.flatten() |> Enum.max_by(...)

1 Like