↓Skip to main content
  1. Posts/

Circle Shift an Array in Elixir

·1 min·

I recently came across a problem in Elixir where I needed to shift a list of items by a given offset aka an “Array Circular shift.”

Other language solutions for this exist on StackOverflow and TheoryApp.

These appear to be implementations of Jon Bentley’s algorithm in Programming Pearls 2nd Edition, which solves the problem in O(n) time.

I wrote an Elixir implementation using Enum.reverse_slice/3

  defmodule ListShift do
    @moduledoc """
    Circle shift a list by a given number of positions in O(n) time.

  An implementation of the algorithm described in Jon Bentley's "Programming Pearls 2nd Edition".

  ## Examples

      iex> ListShift.left([1, 2, 3, 4], 1)
      [2, 3, 4, 1]

      iex> ListShift.left([1, 2, 3, 4], 2)
      [3, 4, 1, 2]

      iex> ListShift.left([1, 2, 3, 4], 3)
      [4, 1, 2, 3]

      iex> ListShift.left([1, 2, 3, 4], 6)
      [1, 2, 3, 4]

      iex> ListShift.left([1, 2, 3, 4], -1)
      [1, 2, 3, 4]
  """

  def left(list, n) when n < 0, do: list

  def left(list, n) do
    size = Enum.count(list)

    list
    |> Enum.reverse_slice(n, size)
    |> Enum.reverse_slice(0, n)
    |> Enum.reverse_slice(0, size)
  end
end

Tested with doctests as follows:

defmodule ListShiftTest do
  use ExUnit.Case
  doctest ListShift
end