From: "Benjamin J. Tilly" <ben_tilly@...>
Date: 2001-03-10T05:17:07+09:00
Subject: [ruby-talk:12356] Re: ...and the challenge

>===== Original Message From gotoken@math.sci.hokudai.ac.jp (GOTO Kentaro) 
=====
>In message "[ruby-talk:12344] Re: ...and the challenge"
>    on 01/03/10, Mathieu Bouchard <matju@sympatico.ca> writes:
>>	n=1_000_000
>>	nums=[]
>>	(0..20).each{|a|
>>		(0..13).each{|b|
>>			(0..9).each{|c|
>>				x = 2**a * 3**b * 5**c
>>				nums << x if x <= n
>>			}
>>		}
>>	}
>>	nums.sort!
>>	nums.each{|x|p x}
>>
>>
>>This takes 0.35 second here.
>>
>>matju
>
>On my machine, yours takes 1.15 sec.
>The following takes 0.55 sec here.
>
>        n=1_000_000
>        nums=[]
>        for a in 0..20
>	  a0 = 2**a
>	  for b in 0..13
>	    b0 = 3**b
>	    for c in 0..9
>	      x = a0 * b0 * 5**c
>	      nums.push x if x <= n
>	    end
>	  end
>	end
>        nums.sort!
>        for x in nums do p x end
>
Try the following out:

    class HammingSeq
      attr_reader :generators
      attr :pos
      attr :seq

      def initialize (*generators)
        if 0 == generators.length
          raise "Cannot create a sequence without generators"
        end
        @generators = generators
        @pos = Array.new (generators.length, 0)
        @seq = [1]
      end

      def [] (n)
        while @seq.length <= n
          @seq.push next_elem
        end
        @seq[n]
      end

      def next_elem
        vals = []
        @pos.each_index {|i|
          vals.push @generators[i] * self[@pos[i]]
        }
        min_val = vals.min
        vals.each_index {|i|
          if min_val == vals[i]
            @pos[i] += 1
          end
        }
        min_val
      end
    end

    hamming = HammingSeq.new(2, 3, 5)
    max = ARGV[0].to_i
    for i in 1..max do
      val = hamming[i]
      if val < max
        puts val
      else
        break
      end
    end
    puts "Done"

That should be fairly efficient. :-)

There is a detailed discussion of how to generalize this problem
at http://perl.plover.com/Stream/stream.html (and the techniques
there are far more general than the one I offered here).

Cheers,
Ben

Cheers,
Ben


-------------------------------------------
The Fastest Browser on Earth now for FREE!!
Download Opera 5 for Windows now! Get it at
http://www.opera.com/download/
-------------------------------------------