DZone Snippets: ruby code

Permutations of letters in a word

mcmire () — Sun, 13 Jul 2008 22:21:49 GMT

I've been programming for a while but for some reason figuring this out was really hard - it took me 2 and a half hours. Unsurprisingly, the solution is extremely simple...



#!/usr/bin/ruby

# permute - takes a word and returns all the permutations of the letters in the word



def permute(word="")

  permutations_among(word.split(//))

end

def permutations_among(letters)

  permutations = []

  if letters.size == 1

    permutations << letters.first

  else

    letters.each_with_index do |letter, i|

      surrounding_letters = letters.dup; surrounding_letters.delete_at(i)

      permutations += permutations_among(surrounding_letters).map {|permutation| letter + permutation }

    end

  end

  permutations

end



permute(ARGV.shift).each {|permutation| puts permutation }

Some benchmarks against other implementations:

* Array#permutations: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/32844
* Array#perm: http://blade.nagaokaut.ac.jp/~sinara/ruby/math/combinatorics/array-perm.rb
* geta: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/139290
* String#perm (based on geta)
* Array#each_permutation: http://knanshon.blogspot.com/2006/08/ruby-permutations.html
* permutation: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/140345


                                              user     system      total        real

permutations_among:                       1.680000   0.010000   1.690000 (  1.700779)

Array#permutations:                       1.740000   0.010000   1.750000 (  1.798288)

geta:                                     2.430000   0.010000   2.440000 (  2.506668)

String#perm:                              2.260000   0.010000   2.270000 (  2.280652)

Array#each_permutation:                   0.820000   0.000000   0.820000 (  0.827463)

permutation:                              2.140000   0.010000   2.150000 (  2.171966)

Benchmark code:



require 'benchmark'



N = 1_000

Benchmark.bm(40) do |x|

  letters = %w(a b c d e)

  string = "abcde"

  x.report("permutations_among:") do

    N.times { permutations_among(letters) }

  end

  x.report('Array#permutations:') do

    N.times { letters.permutations }

  end

  x.report('geta:') do

    N.times { geta(string) }

  end

  x.report('String#perm:') do

    N.times { string.perm }

  end

  x.report('Array#each_permutation:') do

    N.times { letters.each_permutation {|perm| } }

  end

  x.report('permutation:') do

    N.times { 0.upto(string.length.factorial-1) {|i| permutation(string, i)} }

  end

end

So, not bad for a first try ;)

String.random

mcmire () — Mon, 23 Jun 2008 15:58:23 GMT



class String

  def self.random(length=20)

    chars = ('a'..'z').to_a + ('A'..'Z').to_a + ("0".."9").to_a

    hash = ""; length.times { hash << chars[rand(chars.size)] }; hash

  end

end

Perform a Rails find() and iterate over the resulting records in groups

mcmire () — Mon, 05 May 2008 15:35:43 GMT



module ActiveRecord

  class Base

    # This method lets you iterate over the results of a .find, in groups.

    # (Basically an interface to LIMIT.)

    # Anything you can pass as options to .find, you can pass here. 

    # Example 1:

    #   Order.each_by(100, :conditions => { :cc_processed_at => nil }) do |order|

    #     # do stuff with order

    #   end

    # Example 2:

    #   Person.each_by(50, :order => 'name') do |person, index|

    #     # do stuff with person and index

    #   end

    # Pass :update => true in the options to print a message before each group is

    # fetched from the db.

    #

    # Author: Elliot Winkler 

    # Source: http://snippets.dzone.com/posts/show/5461

    def self.each_by(group_size, options={}, &blk)

      update = options.delete(:update) || false

      num_records = count(options.except(:from))

      return 0 if num_records == 0

      #raise "Number of records: #{num_records}"

      also_pass_offset = (blk.arity == 2)

      0.step(num_records, group_size) do |offset|

        find_options = { :offset => offset, :limit => group_size }.merge(options)

        if update

          if num_records == 1

            puts ">> Reading the only record."

          else

            start_offset = offset + 1

            end_offset   = offset + group_size

            end_offset   = num_records if num_records < end_offset

            puts ">> Reading records #{start_offset}-#{end_offset}."

          end

        end 

        find(:all, find_options).each do |record|

          also_pass_offset ? blk.call(record, offset) : blk.call(record)

        end

      end

      num_records

    end

  end

end

Also see:

* http://weblog.jamisbuck.org/2007/4/6/faking-cursors-in-activerecord
* http://weblog.jamisbuck.org/2007/2/28/poor-man-s-pagination