This one was quite hard to solve. I got inspired by how it would be solved with other languages to understand the algorithm and applied it in Ruby.

🧩 Algorithm

Heap’s algorithm generates all possible permutations of n objects. It was first proposed by B. R. Heap in 1963. The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 elements are not disturbed. In a 1977 review of permutation-generating algorithms, Robert Sedgewick concluded that it was at that time the most effective algorithm for generating permutations by computer.

Source

🧩 Example

Input

Input is an array:

array = [1, 2, 3]

Explanation

I want to have all possible permutations with this array, which means

  1. all possible arrays starting with 1: [1, 2, 3] and [1, 3, 2]

  2. then moving the order in the array, switching first and last number for example, from [1, 2, 3] to [3, 2, 1]

  3. all possible arrays starting with 3 now: [3, 2, 1] and [3, 1, 2]

  4. then moving the order in the array from [3, 2, 1] to [2, 1, 3]

  5. all possible arrays starting with 2 now: [2, 1, 3] and [2, 3, 1]

So, for this array, we have 6 possible permutations.

Output

[1, 2, 3]
[1, 3, 2]
[3, 2, 1]
[3, 1, 2]
[2, 1, 3]
[2, 3, 1]

🧩 Code

def permutation(array, n)
  return p array if n == 1

  for i in (0..n-1) do
    permutation(array, n-1)

    if n.even?
      array[i], array[n-1] = array[n-1], array[i]
    else
      array[0], array[n-1] = array[n-1], array[0]
    end
  end
end

🧩 Bonus

In Ruby, this can be simply solved with the permutation method like so :)

a = [1, 2, 3]
a.permutation.to_a
# => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

🧩 Source Code

here :)

Updated: