Instantly share code, notes, and snippets.

# axilleas/perm.rb

Last active February 5, 2022 10:42
Star You must be signed in to star a gist
Permutations of a string
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/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 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
``````