Ruby Implementation of Heap's algorithm for generating all permutations of a collection

README.md

Permutations

This is an implementation of Heap's algorithm for generating the permutations of a collection.

permutations.rb

# coding: utf-8

module Permutations
  def permutations
    acc = []
    generate_permutations(self.count, self.clone, acc)
    acc
  end

  private

  # Heap's algorithm
  # https://en.wikipedia.org/wiki/Heap%27s_algorithm
  #
  def generate_permutations(n, array, acc)
    if n == 1
      acc << array.clone
    else
      for i in 0...n
        generate_permutations(n-1, array, acc)
        j = n.even? ? i : 0
        array[j], array[n-1] = array[n-1], array[j]
      end
    end
  end
end

test_permutations.rb

# coding: utf-8

require "minitest/autorun"
require "./lib/permutations"

class Array
  include Permutations
end

class TestPermutations < Minitest::Test
  def test_responds_to_permutations
    array = []
    assert_respond_to array, :permutations
  end

  def test_permutes_empty_array
    assert_equal [], [].permutations
  end

  def test_permutes_single_element_array
    actual = [1].permutations
    assert_equal [[1]], actual
  end

  def test_permutes_two_element_array
    actual = [1,2].permutations
    expected = [[1, 2], [2, 1]]
    assert_equal expected, actual

  end

  def test_generates_correct_number_of_permutations_for_three_elements
    actual = [1, 2, 3].permutations
    expected = [[1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2], [2, 3, 1], [3, 2, 1]]
    assert_equal expected, actual
  end

  def test_generates_correct_number_of_permutations_for_four_elements
    actual = [1, 2, 3, 4].permutations
    expected =
      [[1, 2, 3, 4],
       [2, 1, 3, 4],
       [3, 1, 2, 4],
       [1, 3, 2, 4],
       [2, 3, 1, 4],
       [3, 2, 1, 4],
       [4, 2, 3, 1],
       [2, 4, 3, 1],
       [3, 4, 2, 1],
       [4, 3, 2, 1],
       [2, 3, 4, 1],
       [3, 2, 4, 1],
       [4, 1, 3, 2],
       [1, 4, 3, 2],
       [3, 4, 1, 2],
       [4, 3, 1, 2],
       [1, 3, 4, 2],
       [3, 1, 4, 2],
       [4, 1, 2, 3],
       [1, 4, 2, 3],
       [2, 4, 1, 3],
       [4, 2, 1, 3],
       [1, 2, 4, 3],
       [2, 1, 4, 3]]

    assert_equal 24, actual.count
    assert_equal expected, actual
  end

  def test_generates_n_factorial_permutations_for_six_elements
    actual = [1, 2, 3, 4, 5, 6].permutations
    assert_equal 720, actual.count
  end
end