Elixir idiom for slicing and mixing two lists

Questions / Help
1

Hello,

I am trying to see if there is a functional approach to the problem that I am trying to do. The way I’m doing it right now is very imperative and using variables a lot.

I am trying to implement Order One crossover for Genetic Algorithm.

Input: two lists of integers of the same length (9)

  • list_1 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
  • list_2 = [9, 3, 7, 8, 2, 6, 5, 1, 4]

Procedure:

  1. Choose two random numbers between 0 and 8 (the length of one list minus one), say, 3 and 6
  2. Make an empty list (or list with a placeholder) of length 9, say result = [nil, nil, nil, nil, nil, nil, nil, nil, nil]
  3. From list_1, take the elements from index 3 and 6, therefore [4, 5, 6, 7], and put it in the result list at the same, index, so becomes [nil, nil, nil, 4, 5, 6, 7, nil, nil]
  4. From list_2, starting from index 6 + 1, and iterate in circular fashion, take an element that is not present yet in result list and append it in a cycle. Sorry if this doesn’t make sense, but basically, since from list_2, the elements starting from index 6 + 1 and cycling it, will be 1, 4, 9, 3, 7, 8, 2, 6, 5, and since we will be taking only numbers that are not present in result, so we will be taking only 1, 9, 3, 8, 2. I have to append these numbers to result starting from index 6 + 1, in circular fashion:
  • [nil, nil, nil, 4, 5, 6, 7, nil, nil]
  • [nil, nil, nil, 4, 5, 6, 7, 1, nil]
  • [nil, nil, nil, 4, 5, 6, 7, 1, 9]
  • [3, nil, nil, 4, 5, 6, 7, 1, 9]
  • [3, 8, nil, 4, 5, 6, 7, 1, 9]
  • [3, 8, 2, 4, 5, 6, 7, 1, 9]

Also, should I post questions like this on Elixir forum or Stack Overflow? Sorry if I shouldn’t post this here.

2

And … where is it?

Looks like an exercise designed to make you use:

Enum.drop/2
Enum.filter/2
Enum.member?/2
Enum.take/2
Kernel.++/2

possibly Enum.slice/3

1 Like
3

Looking at the description (without analysing it too much) it looks like it’s an algorithm that’s supposed to work on arrays. Using lists to do the work of an array, you’re going to have a bad time.

I’ll see if I can be more helpful tomorrow :smiley:

2 Likes
4 
  def genetic_algo(x, y, l1, l2) do
    len = length(l1)
    middle = l1 |> Enum.slice(x, y - x + 1)
    rotated_l2 = (l2 |> Enum.slice(y + 1, len - y)) ++ (l2 |> Enum.slice(0, y))
    filtered_l2 = rotated_l2 |> Enum.reject(& Enum.member?(middle, &1))
    Enum.slice(filtered_l2, x - 1, x) ++ middle ++ Enum.slice(filtered_l2, 0, x - 1)
  end

UPDATE:
Ugly AND NOT working…

SEE UPDATED POST …

SEE @net SOLUTION FOR A NICER WAY

I would not advise the use of ++, because it is slow

iex> Example.genetic_algo(x, y, l1, l2)
[3, 8, 2, 4, 5, 6, 7, 1, 9]
1 Like
5

Right, it is. I’m just wondering if there’s a list-like-fp-like idiom to do this

6

I actually like this. It didn’t occur to me of using slice with the filtered_l2.

Thanks a lot

7

If I understand the algorithm correctly—

def order_one(p1, p2) do
  {i1, i2} = random_range(p1)

  p1_contrib     = Enum.slice(p1, i1..i2)
  p1_contrib_set = MapSet.new(p1_contrib)

  p2_contrib =
    p2 |> shiftl(i2 + 1) |> Enum.reject(&MapSet.member?(p1_contrib_set, &1))

  shiftl(p1_contrib ++ p2_contrib, -i1)
end

defp random_range(list) do
  max_i = length(list) - 1
  [:rand.uniform(max_i), :rand.uniform(max_i)] |> Enum.sort |> List.to_tuple
end

defp shiftl(list, index) do
  {l1, l2} = Enum.split(list, index)
  l2 ++ l1
end
1 Like
8

@kokolegorille That will fail with various other ranges.

G.generic_algo(2, 5, l1, l2)
9

Just wondering what is the benefit of using MapSet?

10

My bad, I messed up with the index

  def genetic_algo(x, y, l1, l2) do
    len = length(l1)
    middle = l1 |> Enum.slice(x, y - x + 1)
    rotated_l2 = (l2 |> Enum.slice(y + 1, len - y)) ++ (l2 |> Enum.slice(0, y))
    filtered_l2 = rotated_l2 |> Enum.reject(& Enum.member?(middle, &1))
    Enum.slice(filtered_l2, len - y - 1, x) ++ middle ++ Enum.slice(filtered_l2, 0, len - y - 1)
  end

iex> Example.genetic_algo(3, 6, l1, l2)                                
[3, 8, 2, 4, 5, 6, 7, 1, 9]
iex> Example.genetic_algo(2, 5, l1, l2)
[8, 2, 3, 4, 5, 6, 1, 9, 7]
11

In theory, lookup performance (in our case). Maps are O(log n), while lists are O(n). However, I ran some benchmarks and it wasn’t until both parents contained upwards of 120 elements that p1_contrib_set started to seriously beat out p1_contrib in the worst case. At shorter lengths p1_contrib performed better.