[Buffalo-pm] Re: [tpm] Bit Counting

[Mike Stok]

On Wed, 1 Oct 2003, Quantum Mechanic wrote:

> I'm looking for an elegant way to generate a list of
> numbers whose binary representation has a given number
> of 1's. I also want to generate this list in numerical
> order.
> 
> For example, with 4 bits on, less than 50:
> 
> 15 1111
> 23 10111
> 27 11011
> 29 11101
> 30 11110
> 39 100111
> 43 101011
> 45 101101
> 46 101110
> 
> Now it's easy enough to check every number up to the
> limit, but it seems there should be a more efficient
> method. On the other hand, the overhead involved in
> "skipping" some numbers may be more expensive than the
> straightforward approach. 
> 
> Anyone have any insights into this?

Just for fun...

[mike at ratdog tmp]$ cat try.rb
#!/usr/bin/env ruby
 
def make_strings (ones, length)
  return if ones > length
   
  if length == 1
    yield ones == 1 ? '1' : '0'
  else
    make_strings(ones,     length - 1) { |s| yield '0' + s }
    make_strings(ones - 1, length - 1) { |s| yield '1' + s } if ones > 0
  end
end
 
ones, limit = ARGV[0].to_i, ARGV[1].to_i
bits = (Math.log(limit + 1) / Math.log(2)).ceil	# need 3 bits for 4
 
make_strings(ones, bits) do |s|
  value = s.to_i(2)		# convert string s to integer (using base 2)
  break if value > limit
  puts "#{s} #{value}"
end

[mike at ratdog tmp]$ ./try.rb 4 50
001111 15
010111 23
011011 27
011101 29
011110 30
100111 39
101011 43
101101 45

Mike

-- 
mike at stok.co.uk                    |           The "`Stok' disclaimers" apply.
http://www.stok.co.uk/~mike/       | GPG PGP Key      1024D/059913DA 
mike at exegenix.com                  | Fingerprint      0570 71CD 6790 7C28 3D60
http://www.exegenix.com/           |                  75D2 9EC4 C1C0 0599 13DA