रूबी

Question

में सर्वश्रेष्ठ क्रमपरिवर्तन गिनती एल्गोरिदम मैं बाइनरी रूप में 1 और 0 के पी संख्या द्वारा व्यक्त की गई संख्याओं की संख्या को गिनने की कोशिश कर रहा हूं। पी = 2 है, तो संख्या व्यक्त कर रहे हैं 0011, 1100, 0110, 0101, 1001, 1010, इसलिए गिनती 6.

मैंने कोशिश की है:

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

लेकिन यह के लिए सबसे अच्छा समाधान नहीं है बड़ी संख्या (पी < = 30 हो सकता है)।

सर्वश्रेष्ठ क्रमपरिवर्तन तकनीक क्या हो सकती है, या क्या हमारे पास ऐसा करने के लिए कोई सीधा आगे गणित है?

Answer 1

Number of permutation can be calculated using factorial.

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

दोहराया आइटम गिनती करने के लिए, आप 2 के साथ ऊपर विभाजित करने के लिए की जरूरत है! और 2! (2 => 0 की संख्या, 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 

---

दिया p के लिए, वहाँ (p*2)! क्रमपरिवर्तन है/और दूर करने के लिए (p! * p!) द्वारा विभाजित किया जाना चाहिए डुप्लिकेशन:

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