How to swap elements in a list?

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

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.

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.

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

Edit:
https://github.com/elixir-lang/elixir/blob/master/lib/elixir/lib/enum.ex#L2762

@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.

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

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:
https://github.com/erlang/otp/blob/00503c64bc321fc1d2ff1233613debf2f579cedb/lib/stdlib/src/array.erl#L108-L126

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.

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.

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.

I tough recursion will be the most performant way here and I think it is but implementation is quite long.
It’s still O(n) but probably 2x as performant as twice using replace_at

defmodule ListSwap do
  def swap(list, i, j) when i >= 0 and j >= 0 do
    # Ensure i is smaller than j
    {i, j} = if i <= j, do: {i, j}, else: {j, i}
    swap_pop(list, i, j, 0, [], nil)
  end

  defp swap_pop([], _i, _j, _current, _acc, _temp), do: raise("index out of bounds")

  # When we reach index i, store the element in temp
  defp swap_pop([hd | tl], i, j, i, acc, nil), do: swap_pop(tl, i, j, i + 1, acc, hd)

  # When we reach index j, swap with stored i element and start to go back
  defp swap_pop([hd | tl], i, j, j, acc, tmp), do: swap_push([tmp | tl], i, j, j - 1, acc, hd)

  # just move elements to accumulator
  defp swap_pop([hd | tl], i, j, curr, acc, tmp),
    do: swap_pop(tl, i, j, curr + 1, [hd | acc], tmp)

  # return reversed list
  defp swap_push(list, _i, _j, 0, [], nil), do: list

  # when replacing 0 with 1 edge case 
  defp swap_push(list, i, j, 0, [], tmp), do: swap_push([tmp | list], i, j, 0, [], nil)

  # replace i with stored j
  defp swap_push(tl, i, j, i, [hd | acc], tmp),
    do: swap_push([hd, tmp | tl], i, j, i - 1, acc, nil)

  # just push from acc to list
  defp swap_push(tl, i, j, curr, [hd | acc], tmp),
    do: swap_push([hd | tl], i, j, curr - 1, acc, tmp)
end