我正在尝试计算由二进制形式的 1 和 0 的 P 数表示的数字的数量。如果P = 2,则表示的数字为0011、1100、0110、0101、1001、1010,所以计数为6。
我试过:
[0,0,1,1].permutation.to_a.uniq
但这不是大数的最佳解决方案(P 可以 <= 30)。
什么可能是最好的排列技术,或者我们是否有任何直接的数学来做到这一点?
最佳答案
Number of permutation can be calculated using factorial.
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
关于arrays - ruby 中的最佳排列计数算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44868252/