algorithm - Ruby: calculating number of unique permutations without using .permutation with duplicates in data set -

i require method taking in string of varying length , content, returning number of permutations without repetition. have written following try solve problem

def permutations(n)   k = n.to_s.chars.uniq.length   e = n.to_s.length   m = (1..e).reduce(1, :*)   p = (1..k).reduce(1, :*)   l = m / p   case     when k == 1 1     when k < e l     else m    end end  

the above returning results i've been confused couple of days i've realised occur there more 1 set of duplicate values uniq check.

if pass through bbbb789 210 correct. if have set 2 duplicates such 73839 expected result 60 reach 5

i realised yesterday issues can't find way factor in duplicates

also first method solving use

k = n.to_s.chars.uniq.length m = n.to_s.chars.length  return 1 if k <= 1  n.to_s.chars.permutation(m)to_a.uniq.size 

this worked takes age cycle through permutations of longer sets

tl;dr:

def factorial(n)   (1..n).inject(1, :*) end  str = '73839'  # https://stackoverflow.com/questions/5470725/how-to-group-by-count-in-array-without-using-loop chars_count = str.split('').inject(hash.new(0)) { |h, e| h[e] += 1 ; h }  # https://stackoverflow.com/questions/9560335/ruby-hash-to-array-of-values chars_fact = chars_count.values.inject(1) {|result, element| result*factorial(element)}  p "there #{factorial(str.length)/chars_fact} permutations without duplicates." 

not explanation :

well, math problem:

note : when write n! should read "factorial n" , represents integer 1*2*...*n . can find ruby implementation here : https://stackoverflow.com/a/12415362/4480140

if had n a's , m b's formula find number of permutations without duplicates n choose m+n (m+n)!/(n!*m!).

then, if have 'aazzerty' have a's , b's. have 'aabbbbbb', have 2 choose 8 ways of permuting. 1 of possible permutations 'bbabbbab'. permute b's. know these b's contain 2 z's , 1 of (e,r,t,y). permute not z or a. have 2 choose 6 ways of doing that. repeat process ...

in end number of permutations (2 choose 8)(2 choose 6)(1 choose 4)...(1 choose 2). can cancel out, in fact 8!/(2!*2!*1!*1!*1!*1!).

basically, have count number of each character, take factorial of numbers, multiply them together. that's denominator, , numerator factorial length of string.