# Swap elements in a list

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]

``````

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

1 Like

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.

1 Like

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

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

Edit:

@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
``````
1 Like

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

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

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 `i1`th element until itâ€™s seen the `i2`th.

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

1 Like