Best permutation count algorithm in ruby

Question

I am trying to count the number of numbers that are expressed by P number of 1's and 0's in binary form. If P = 2, then the numbers expressed are 0011, 1100, 0110, 0101, 1001, 1010, so the count is 6.

I tried:

[0,0,1,1].permutation.to_a.uniq

But it is not the best solution for big numbers (P can be <= 30).

What could be the best permutation technique, or do we have any straight forward math to do this?

Answer 1

Number of permutation can be calculated using factorial.

a = [0, 0, 1, 1]
(1..a.size).inject(:*)  # => 4! => 24

to count duplicated item, you need to divide above with 2! and 2! (2 => number of 0s, 1s)

---

=> 4! / (2! * 2!) => 6

class Fixnum
  def factorial
    (1..self).inject(:*)
  end
end

a.size.factorial / a.group_by(&:itself).map { |k, v| v.size.factorial }.inject(:*)
=> 6

---

For the given p, there's (p*2)! permutations / and should be divided by (p! * p!) to remove duplication:

p = 2
(p*2).factorial / (p.factorial ** 2)                                               
# => 6