数组 – ruby??中的最佳置换计数算法

发布时间：2020-12-16 22:56:46 所属栏目：百科来源：网络整理

导读：我试图用二进制形式计算由P数1和0表示的数字的数量.如果P = 2,则表示的数字是0011,1100,0110,0101,1001,1010,因此计数为6. 我试过了： [0,1,1].permutation.to_a.uniq 但它不是大数字的最佳解决方案(P可以= 30). 什么是最好的排列技术,还是我们有任何直接的

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

我试过了：

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

但它不是大数字的最佳解决方案(P可以<= 30). 什么是最好的排列技术,还是我们有任何直接的数学来做到这一点？

解决方法

Number of permutation can be calculated using factorial.

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

计算重复项目,你需要用2分！和2！ (2 => 0s,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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!