Skip to content

Instantly share code, notes, and snippets.

@axilleas
Last active Feb 5, 2022
Embed
What would you like to do?
Permutations of a string
#!/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
@aslam
Copy link

aslam commented Feb 5, 2022

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment