红宝石中的最佳排列计数算法

我想计算以二进制形式表示的P数为1和0的数字的数量。如果P = 2，则表示该数字是0011，1100，0110，0101，1001，1010，所以计数为6红宝石中的最佳排列计数算法

我尝试：

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

但它不是最好的解决方案大数字（P可以是< = 30）。

什么可能是最好的置换技术，或者我们有任何直接的数学来做到这一点？

来源

2017-07-02 Yusuf

小数如何与您的问题相关？它看起来不像。 – sawa

P等于或小于30的事实如何影响大数的计算？ P变大时不是那么严重吗？ – sawa

@sawa问题的其他部分涉及小数限制A，B。 E.g.我们需要根据给定范围A，B打印计数。例如。对于相同的例子A = 5，B = 10，P = 2，那么我在这个范围内只有4个值（除了3和12） – Yusuf

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

来源

2017-07-02 07:20:36 falsetru

组合挑战的读者：对于p = 3，想象1（0's）白色）块编号为1,2和3.这6块可以订购6！方法。现在考虑这6个中的任何一个！排序（例如，w3，b1，b3，w1，w2，b2）。如果我们只关心颜色的顺序，我们可以问一下这个顺序中的黑块可以重新排序的方式。有三种方法可以选择第一个块，对于其中的每个块，有两种方法可以对其他两个黑块进行排序。因此，有3！ = 6个黑色块的颜色保留排序... –

...对于每个排序有3个！白色块的颜色保留顺序。因此，对于给定的6个块的序列，有3！* 3！颜色保持排序的块，这就是为什么分裂（2p）！由p！* p！以获得期望的排列数量。 –

@CarySwoveland，谢谢你的亲切解释！ – falsetru

红宝石中的最佳排列计数算法

回答

相关问题