1

I require a method for taking in a string of varying length and content, returning the number of permutations without repetition. I have written the following to try to solve this 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 then 1
    when k < e then l
    else m 
  end
end

The above is returning some results that I've been confused by for a couple of days which I've realised occur where there are more than 1 set of duplicate values for uniq to check.

If I pass through bbbb789 I get 210 which is correct. However if I have a set with two duplicates such as 73839 the expected result is 60 but I reach 5

I realised yesterday where the issues were but I can't find a way to factor in the duplicates

Also my first method for solving this was to 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 also worked but takes an age to cycle through all permutations of longer sets

Aetherus
  • 8,720
  • 1
  • 22
  • 36
Oscady
  • 93
  • 10
  • Fixed the indentation and added 2 `end`. – Aetherus May 25 '16 at 09:21
  • @Aetherus you can provide an _edit summary_ when editing questions, right before the _Save Edits_ button. – Stefan May 25 '16 at 09:49
  • 3
    The problem you have with your formula is that you are counting the number of unique characters but you need the information on the number of occurences of each character. For instance 'aabb' and 'abbb' both have the same number of characters and the same number of distinct characters, yet they have respectively 6 and 4 permutations without duplicates. – Pholochtairze May 25 '16 at 10:18

1 Answers1

2

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 are #{factorial(str.length)/chars_fact} permutations without duplicates."

Not very good explanation :

Well, this is mostly a math problem:

Note : When I write n! you should read "factorial n" and it represents the integer 1*2*...*n . You can find a ruby implementation here : https://stackoverflow.com/a/12415362/4480140

If you had n a's and m b's then the formula to find the number of permutations without duplicates is n choose m+n which is (m+n)!/(n!*m!).

Then, what we do if we have 'aazzerty' is we say we have a's and b's. So we have 'aabbbbbb', we have 2 choose 8 ways of permuting. One of the possible permutations would be 'bbabbbab'. Then we permute the b's. We know that these b's contain 2 z's and 1 of (e,r,t,y). We will permute everything that is not a z or an a. We have 2 choose 6 ways of doing that. We repeat the process ...

In the end the number of permutations is (2 choose 8)(2 choose 6)(1 choose 4)...(1 choose 2). We can cancel out, in fact we get 8!/(2!*2!*1!*1!*1!*1!).

Basically, we have to count the number of each character, take the factorial of all those numbers, multiply them together. That's the denominator, and the numerator is factorial the length of the string.

Community
  • 1
  • 1
Pholochtairze
  • 1,836
  • 1
  • 14
  • 18
  • `inject` takes an optional initial value, so instead of appending `|| 1`, you can write `inject(1, :*)` – Stefan May 25 '16 at 09:54
  • Thank you for your detailed response, that's definitely helped my mind cope. May I ask, if I were to extend the `k = ...uniq` to then count the number of each unique character and include the result in the object `l` to be divided by the factorial length of the string... would that solve the duplicate values problem? – Oscady May 25 '16 at 10:06
  • Basically the formula is : `(length of the string)!/( (char_1_count)!*(char_2_count)!*...*(char_n_count)! )`. Where char_1_count represent the total number of times char_1 occurs in the string, for instance in 'aab' is char_1='a' then char_1_count=2. As long as you do that it will work. – Pholochtairze May 25 '16 at 10:14
  • @Pholochtairze thanks. I'll have a look into counting each non unique character occurrence now. I had an ideasomething similar would be needed but it was giving me a headache trying to implement it without understanding fully – Oscady May 25 '16 at 10:36