Swap elements in a list

Questions / Help
1

Is there a better way to swap elements in a list?
Any inbuilt function or a library?

defmodule SwapElements do
  def swap(list, first_index, second_index) do
    {a, b} = split(list, first_index + 1)
    {x, y} = split(b, second_index - first_index)

    [h1 | t1] = a
    [h2 | t2] = x

    y
    |> reverse_append([h1])
    |> reverse_append(t2)
    |> reverse_append([h2])
    |> reverse_append(t1)
  end

  def split(list, n) do
    split([], list, n)
  end

  def split(a, b, 0) do
    {a, b}
  end

  def split(list, [h|t], n) do
    split([h | list], t, n - 1)
  end

  def reverse_append(list, []) do
    list
  end

  def reverse_append(list, [h | t]) do
    reverse_append([h | list], t)
  end
end

iex(27)> SwapElements.swap(Enum.to_list(0..10), 1, 4)        
[0, 4, 2, 3, 1, 5, 6, 7, 8, 9, 10]
2

Shower Thought:
If lists in beam were implemented as XOR linked list
They can be be reversed in O(1)

1 Like
4

Here are two possible approaches using functions from Enum and List:

defmodule Swap do
  def swap(a, i1, i2) do
    {first, [e1 | middle]} = Enum.split(a, i1)
    {middle, [e2 | rest]} = Enum.split(middle, i2-i1-1)
    List.flatten([first, e2, middle, e1, rest])
  end
end

defmodule Swap2 do
  def swap(a, i1, i2) do
    e1 = Enum.at(a, i1)
    e2 = Enum.at(a, i2)

    a
    |> List.replace_at(i1, e2)
    |> List.replace_at(i2, e1)
  end
end

Beware that both of these (just like the one in your post) have O(N) time-complexity since they have to traverse the entire list.

2 Likes
5

Swap2 is definitely the most clear imho, nice stuff.

@sarat1669 It’s probably worth noting that if you want to perform a bunch of index based changes to a “list” you are probably better off using a map with the indices as keys rather than a list, which just really isn’t setup for efficient index based access or changes.

1 Like
6

@al2o3cr Enum.split will be doing a Enum.reverse internally right?
I was trying to avoid that

Edit:

7

@benwilson512 I think the ordering will not be maintained in a Map.
It might be a good alternative for accessing and updating and not for the other cases.

8

You could also use the :array module from Erlang.

defmodule ErlangSwap do
  def swap(a, i1, i2) do
    a = :array.from_list(a)

    v1 = :array.get(i1, a)
    v2 = :array.get(i2, a)
    
    a = :array.set(i1, v2, a)
    a = :array.set(i2, v1, a)
    
    :array.to_list(a)
  end
end
2 Likes
9

It’s a tradeoff between reducing the constant factor of an O(N) algorithm versus readability.

If performance is a concern, the better solution is to pick a more-efficient data structure for the operations you want to do. For instance, the :array module mentioned by @egze uses a 10-way tree made of tuples. The source has some additional notes about why they chose 10:

Also note that :array.from_list and :array.to_list both have to traverse the whole list, so if you’re doing a lot of swaps you’ll want to keep your data in the :array structure.

1 Like
10

There are a couple of libraries implementing such higher-performance persistent sequential data structures. A couple of years back I wrote Arrays which has a single interface with pluggable backends for either :arrays or “maps with indices as keys”, as well as implementing many useful protocols like Enumerable, Collectable, Access, etc. to allow you to keep your code idiomatic and easily change between one Enumerable backend and another.

Other algorithms exist as well. For instance, there is a library called Hallux that has a sequential data structure with amortized O(1) element access based on finger trees, and PersistentVector based on 32-way tries.

1 Like
11

I don’t know when this would ever be useful, but here’s a version of swap that even works on infinite streams!

defmodule Swap3 do
  def swap(a, i1, i2) do
    a
    |> Stream.with_index()
    |> Stream.transform(:start, &do_swap(&1, &2, i1, i2))
  end

  defp do_swap({el, idx}, :start, i1, _) when idx < i1 do
    {[el], :start}
  end

  defp do_swap({el, idx}, :start, i1, _) when idx == i1 do
    {[], {el, []}}
  end

  defp do_swap({el, idx}, {first_el, acc}, _, i2) when idx < i2 do
    {[], {first_el, [el | acc]}}
  end

  defp do_swap({second_el, idx}, {first_el, acc}, _, i2) when idx == i2 do
    result = Stream.concat([[second_el], Enum.reverse(acc), [first_el]])
    {result, :end}
  end

  defp do_swap({el, _}, :end, _, _) do
    {[el], :end}
  end
end

This uses Stream.transform with a reducer function that implements a tiny state machine to handle the change in behavior when the two indexes are passed.

It also chains:

Stream.iterate(0, &(&1 + 1))
|> Swap3.swap(5, 12)
|> Swap3.swap(2, 18)
|> Swap3.swap(7, 13)
|> Stream.take(20)
|> Enum.to_list()

# gives
[0, 1, 18, 3, 4, 12, 6, 13, 8, 9, 10, 11, 5, 7, 14, 15, 16, 17, 2, 19]

While it’s a streaming algorithm, it still needs to hold at least i2-i1 intermediate elements in memory since it can’t produce the i1th element until it’s seen the i2th.

Also beware: Swap3.swap does weird things if the supplied indexes aren’t in order (i1 < i2) or are equal.

1 Like