#
# Recursion generating all valid 5 length permutations.
#
def patterns(pattern, i)
  if pattern.length == 5
    p_p pattern and return
  end

  (1..5).each do |v|
    if is_valid(pattern[0...i], v)
      pattern[i] = v
      patterns Array.new(pattern), i+1
    end
  end
end

#
# Checking if value can be appended to the pattern
#
def is_valid(pattern, value)
  # value can not be appended if value if already in the pattern
  return false unless (pattern & [value]).empty?

  # value can not be appended if adding the value would result
  # in a decreasing/increasing sequence of length 3
  return false if (pattern.length > 1) && ((pattern[-1] - value) * (pattern[-2] - pattern[-1]) == 1)

  true
end

def p_p(pattern)
  p "#{pattern} with #{(pattern.select.with_index { |e, i| e != i + 1 }.length / 2.0).round} transpositions"
end

patterns Array.new, 0


<<-RESULTS
  [1, 2, 4, 3, 5] with 1 transpositions
  [1, 2, 4, 5, 3] with 2 transpositions
  [1, 2, 5, 3, 4] with 2 transpositions
  [1, 3, 2, 4, 5] with 1 transpositions
  [1, 3, 2, 5, 4] with 2 transpositions
  [1, 3, 4, 2, 5] with 2 transpositions
  [1, 3, 5, 2, 4] with 2 transpositions
  [1, 3, 5, 4, 2] with 2 transpositions
  [1, 4, 2, 3, 5] with 2 transpositions
  [1, 4, 2, 5, 3] with 2 transpositions
  [1, 4, 3, 5, 2] with 2 transpositions
  [1, 4, 5, 2, 3] with 2 transpositions
  [1, 4, 5, 3, 2] with 2 transpositions
  [1, 5, 2, 4, 3] with 2 transpositions
  [1, 5, 3, 2, 4] with 2 transpositions
  [1, 5, 3, 4, 2] with 1 transpositions
  [1, 5, 4, 2, 3] with 2 transpositions
  [2, 1, 3, 5, 4] with 2 transpositions
  [2, 1, 4, 3, 5] with 2 transpositions
  [2, 1, 4, 5, 3] with 3 transpositions
  [2, 1, 5, 3, 4] with 3 transpositions
  [2, 3, 1, 4, 5] with 2 transpositions
  [2, 3, 1, 5, 4] with 3 transpositions
  [2, 3, 5, 1, 4] with 3 transpositions
  [2, 3, 5, 4, 1] with 2 transpositions
  [2, 4, 1, 3, 5] with 2 transpositions
  [2, 4, 1, 5, 3] with 3 transpositions
  [2, 4, 3, 1, 5] with 2 transpositions
  [2, 4, 3, 5, 1] with 2 transpositions
  [2, 4, 5, 1, 3] with 3 transpositions
  [2, 4, 5, 3, 1] with 3 transpositions
  [2, 5, 1, 3, 4] with 3 transpositions
  [2, 5, 1, 4, 3] with 2 transpositions
  [2, 5, 3, 1, 4] with 2 transpositions
  [2, 5, 3, 4, 1] with 2 transpositions
  [2, 5, 4, 1, 3] with 3 transpositions
  [3, 1, 2, 4, 5] with 2 transpositions
  [3, 1, 2, 5, 4] with 3 transpositions
  [3, 1, 4, 2, 5] with 2 transpositions
  [3, 1, 4, 5, 2] with 3 transpositions
  [3, 1, 5, 2, 4] with 3 transpositions
  [3, 1, 5, 4, 2] with 2 transpositions
  [3, 2, 4, 1, 5] with 2 transpositions
  [3, 2, 4, 5, 1] with 2 transpositions
  [3, 2, 5, 1, 4] with 2 transpositions
  [3, 2, 5, 4, 1] with 2 transpositions
  [3, 4, 1, 2, 5] with 2 transpositions
  [3, 4, 1, 5, 2] with 3 transpositions
  [3, 4, 2, 1, 5] with 2 transpositions
  [3, 4, 2, 5, 1] with 3 transpositions
  [3, 5, 1, 2, 4] with 3 transpositions
  [3, 5, 1, 4, 2] with 2 transpositions
  [3, 5, 2, 1, 4] with 3 transpositions
  [3, 5, 2, 4, 1] with 2 transpositions
  [3, 5, 4, 1, 2] with 3 transpositions
  [3, 5, 4, 2, 1] with 3 transpositions
  [4, 1, 2, 5, 3] with 3 transpositions
  [4, 1, 3, 2, 5] with 2 transpositions
  [4, 1, 3, 5, 2] with 2 transpositions
  [4, 1, 5, 2, 3] with 3 transpositions
  [4, 1, 5, 3, 2] with 3 transpositions
  [4, 2, 1, 3, 5] with 2 transpositions
  [4, 2, 1, 5, 3] with 2 transpositions
  [4, 2, 3, 1, 5] with 1 transpositions
  [4, 2, 3, 5, 1] with 2 transpositions
  [4, 2, 5, 1, 3] with 2 transpositions
  [4, 2, 5, 3, 1] with 2 transpositions
  [4, 3, 1, 2, 5] with 2 transpositions
  [4, 3, 1, 5, 2] with 3 transpositions
  [4, 3, 5, 1, 2] with 3 transpositions
  [4, 3, 5, 2, 1] with 3 transpositions
  [4, 5, 1, 3, 2] with 3 transpositions
  [4, 5, 2, 1, 3] with 3 transpositions
  [4, 5, 2, 3, 1] with 3 transpositions
  [4, 5, 3, 1, 2] with 2 transpositions
  [5, 1, 2, 4, 3] with 2 transpositions
  [5, 1, 3, 2, 4] with 2 transpositions
  [5, 1, 3, 4, 2] with 2 transpositions
  [5, 1, 4, 2, 3] with 3 transpositions
  [5, 2, 1, 3, 4] with 2 transpositions
  [5, 2, 1, 4, 3] with 2 transpositions
  [5, 2, 3, 1, 4] with 2 transpositions
  [5, 2, 4, 1, 3] with 2 transpositions
  [5, 2, 4, 3, 1] with 2 transpositions
  [5, 3, 1, 2, 4] with 3 transpositions
  [5, 3, 1, 4, 2] with 2 transpositions
  [5, 3, 2, 4, 1] with 2 transpositions
  [5, 3, 4, 1, 2] with 3 transpositions
  [5, 3, 4, 2, 1] with 3 transpositions
  [5, 4, 1, 3, 2] with 3 transpositions
  [5, 4, 2, 1, 3] with 3 transpositions
  [5, 4, 2, 3, 1] with 3 transpositions
RESULTS