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 permutationgenerating algorithms, Robert Sedgewick concluded that it was at that time the most effective algorithm for generating permutations by computer.
🧩 Example
Input
Input is an array:
array = [1, 2, 3]
Explanation
I want to have all possible permutations with this array, which means

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

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

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

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

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..n1) do
permutation(array, n1)
if n.even?
array[i], array[n1] = array[n1], array[i]
else
array[0], array[n1] = array[n1], 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]]