Permutations of a string

perm.rb

#!/usr/bin/env ruby

# Recursive method, print all strings permutations with length = str.length.
# Iterrate over each character of given string and recursively call
# string_permutations. Each time, a letter from str is stripped and added to elmt.
# When str.length reaches zero, print elmt.
def string_permutations(str, elmt='')
  if str.length == 0
    p [elmt]
  else
    str.each_char do |char|
      string_permutations(str.chars.reject {|x| x == char}.join, elmt + char)
    end
  end
end

# Calculate factorial of n.
def factorial(n)
  n <= 1 ? 1 : (1..n).reduce(:*)
end

str = 'abce'

# Using ruby's Array#permutation method, store in an array all possible
# permutations of length = str.length
all_strings = str.chars.permutation(str.length).map { |char| char.join'' }

# Number of possible permutations including all chars.
possible_permutations = factorial(str.length)

# Call recursive function
string_permutations(str)

# Silly test to make sure the number of possible permutations generated
# is equal to the factorial of number of chars. Call uniq on all strings
# to be more certain we have no double values.
p possible_permutations == all_strings.uniq.count

Thanks for this. However, there seems to be a bug where the permutations are wrong if a character is repeated in the original string. We can reject by the index for fix it:

def string_permutations(str, elmt='')
  if str.length == 0
    p [result]
  else
    str.each_char.with_index do |char, i|
      permutations(str.chars.reject.with_index { |_, j| i == j }.join, result + char)
    end
  end
end