Return all permutations of a string, without any duplicates.

string_permutations.rb

require 'set'

# First I wanted to get an idea of the timing of the various approaches
def time
  start = Time.now
  yield
  puts Time.now.to_f - start.to_f
end

# This optimizes for redundant strings of values, front-loading them to maximize duplicates
def optimize(x)
  references = {}
  x.each do |ch|
    references[ch] ||= 0
    references[ch] += 1
  end
  sorted = references.sort {|b,a| (a.last <=> b.last) }
  sorted.inject([]) { |accum,pair| accum + [pair.first] * pair.last }
end

# Reduce the string to an array and then do a more typical permutation on the array.
def permute_string(x)
  permutations(optimize(x.chars.to_a)).to_a
end

# The core algorithm, essentially repeatedly growing a set with
# the next character inserted at all valid locations in all entries
# in the previous set.  Duplicates are added, but culled by the set,
# so while the work to generate them is done, work to expand them by
# later characters is not.
#
def permutations(x)
  return x if x.empty?
  ch = x.delete_at(0)
  underlying = Set.new([ch])
  x.each do |ch|
    new_set = Set.new
    underlying.each do |permutation|
      (0..permutation.length).each do |idx|
        new_set.add(permutation.dup.insert(idx, ch))
      end
    end
    underlying = new_set
  end
  underlying.each
end

# Some straightforward test methods
# First, let's compare with Ruby's built in permutation method.
time { puts permute_string('baaabcddb').length }
# 5040 in 0.017 seconds on my system
time { puts 'baaabcddb'.chars.to_a.permutation(9).to_a.uniq.length }
# 5040 in 2.83 seconds on my system

# Now let's show some basic queries (sorted when useful, just so it's consistent).
puts permute_string('a').inspect
# ["a"]
puts permute_string('ab').sort.inspect
# ["ab", "ba"]
puts permute_string('abc').sort.inspect
# ["abc", "acb", "bac", "bca", "cab", "cba"]

# Let's look at duplicate management
puts permute_string('aaaaaaaaaaa').inspect
# ["aaaaaaaaaaa"]
puts permute_string('aaaaaaaaab').sort.inspect
# ["aaaaaaaaab", "aaaaaaaaba", "aaaaaaabaa", "aaaaaabaaa", "aaaaabaaaa", "aaaabaaaaa", "aaabaaaaaa", "aabaaaaaaa", "abaaaaaaaa", "baaaaaaaaa"]

# Empty string has no permutations
puts permute_string('').inspect
# []

Awesome repo - first one I found that worked correctly and quickly.