Ruby'de en iyi permütasyon sayımı algoritması

Question

1'lerin P sayısı ve 0'ın ikili biçimiyle ifade edilen sayıların sayısını saymaya çalışıyorum. P = 2, sonra ifade sayıları 0011, 1100, 0110, 0101, 1001, 1010, böylece sayımı denedim 6.

olduğunu şunlardır:

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

Ama parasını en iyi çözüm değildir büyük sayılar (P < = 30 olabilir).

En iyi permütasyon tekniği ne olabilir, yoksa bunu yapmak için herhangi bir düz matematik var mı?

Answer 1

Number of permutation can be calculated using factorial.

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

çoğaltılamaz öğeyi saymak, sen 2 ile yukarıdaki bölmek gerekiyor! ve 2! (0s 2 => numarası, 1s)

---

=>4!/(2! * 2!) =>p verilen için

---

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

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

, orada (p*2)! permütasyon var/ve kaldırmak için (p! * p!) bölünmelidir çoğaltma:

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