ruby中的最佳置换计数算法

Question

我试图用二进制形式计算由P数1和0表示的数字的数量.如果P = 2,则表示的数字是0011,1100,0110,0101,1001,1010,因此计数为6.

我试过了:

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

但它不是大数字的最佳解决方案(P可以<= 30).

什么是最好的排列技术,还是我们有任何直接的数学来做到这一点？

Answer 1

可以使用阶乘计算排列数.

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

计算重复项目,你需要用2分!和2!(2 => 0的数量,1)

=> 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

对于给定的p,存在(p*2)!排列/并且应该除以(p! * p!)删除重复:

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