Ruby ２進数の１を１０万回早く数える方法について

Question

######問題
入力にaとbがあるとして1からaの回数分２進数に変換して01で表示されているの物の中から1の数がb個の物だけを数えたいとします。
例.
a=10 b=2の場合、1の数が2個なのは
11, 101, 110, 1001, 1010なので
答えは5となる。
でこれがa=100000 b=17（答え：０回）の場合が知りたいのですが
######自分なりに考えた結果

a = 100000
b = 17
cnt = 0
(1..a).each do |i|
    ans = i.to_s(2).split(//)
    ans = ans.map(&:to_i)
    ans = ans.inject(:+)
    if ans == b
        cnt += 1
    end
end
puts cnt

と自分なりに考えたりググってみたりでコーディングしたのですが、これだと処理時間がかかりすぎるといわれてしまいます。
######聞きたいこと
上記よりも早く処理ができる記述の仕方を教えて頂きたいです。
お手数ではありますがよろしくお願いします。

Answer 1

require 'benchmark'

Benchmark.bm 0 do |r|
    r.report do
        a = 100000
        b = 17
        cnt = 0
        (1..a).each do |i|
            ans = i.to_s(2).split(//)
            ans = ans.map(&:to_i)
            ans = ans.inject(:+)
            if ans == b
                cnt += 1
            end
        end
        puts cnt
    end
    r.report do
        a = 100000
        b = 17
        puts (1..a).map{|i| i.to_s(2).scan(/1/).size == b }.select{|i|i}.size
    end
    r.report do
        a = 100000
        b = 17
        puts (1..a).map{|i| i.to_s(2).scan(/1/).size}.select{|i|i == b}.size
    end
end

半分以下の時間で計算できそうです

Comments

[xekid]

回答頂き本当にありがとうございます。
このコードは是非今後の参考にさせて頂きます。

Answer 2

100000と17の場合は、コードに起こすまでもなく、暗算でできます。

二進法で表現して1が17個になる最小の数は1（2の0乗）＋2（2の1乗）＋…＋65536（2の16乗）ですが、これは131071と、100000を超えてしまいます。つまり、100000未満には1つもありません。

---

（combinationで書いたコード）

a = 1_000_000
b = 17

p (0..(a.bit_length - 1)).to_a.combination(b)
  .map{ |arr| arr.map{ |i| 2**i }.reduce(&:+) }
  .select{ |num| num <= a }.length

Comments

[xekid]

最速の回答有難うございます。
そもそもコーディングで回すのがナンセンスってことですね。
参考にさせて頂きます。
ちなみになんですが、もしRubyでコーディングするのなら上記の記述で問題はないでしょうか？
初心者なもので正解というか参考になる記述が知りたいのですが分かるようでしたら教えて頂けると有難いです。

[maisumakun]

大きく分けて、2つの作戦があります。

・分割統治法（「最上位のビットを立てるか立てないか」で分岐して、1桁範囲の狭い問題にしていく）
・Array#combinationで「何ビット目を立てるか」の組み合わせを生成しておいて、大きさチェックを行う

[maisumakun]

試しに書いてみました（急いで書いたので、読みづらいかもしれません）。

[xekid]

回答有難うございます。
貴重なご意見本当にありがとうございます。

Answer 3

例えば
0b00000 ～ 0b11100 の範囲であれば、

0b0???? (0b00000 to 0b01111)
0b10??? (0b10000 to 0b10111)
0b110?? (0b11000 to 0b11011)
0b11100 (0b11100)

のように分割して考えられます。
0b0????のうち1が2つ含まれる組み合わせは combination(4,2) で計算すれば良いので
全部列挙するよりは早いと思います。

コードはちょっと汚いですが・・・。

a = 10000000
b = 11

def factorial(n)
  return 1 if n == 0
  return (1..n).inject(:*)
end

def permutation(n, r)
  return 1 if n == 0
  s = n - r + 1
  return (s..n).inject(:*)
end

def combination(n, r)
  r = [r, n - r].min
  return n if r == 1
  return 1 if r == 0
  return permutation(n, r) / factorial(r)
end

num_left1 = 0
ans = 0
(a.bit_length-1).downto(0) { |pos|
  if ( a[pos] == 1 ) then
    length_rightside = pos
    num_right1 = b - num_left1
    if ( num_right1 >= 0 && length_rightside >= num_right1 ) then
      ans += combination(length_rightside,num_right1)
    end
    num_left1 += 1
  end
}
ans += 1 if num_left1 == b

puts ans

たいていの入力に対して計算はすぐに終わると思います。