A subset of Ruby (16 Apr 2006)

A programming language which inspires an author to write something like why's (poignant) guide to Ruby must be truly special. So I gave in readily to the temptation to try the language, especially since Ruby's dynamic type system and lambda-like expressions appeal to the Lisp programmer in me.

A while ago, I blogged about the subset sum problem, and so writing a version of that algorithm in Ruby was an obvious choice.

$solutions = 0
$numbers = []
$flags = []

def find_solutions(k, target_sum)
  if target_sum == 0
    # found a solution!
    (0..$numbers.length).each { |i| if ($flags[i]) then print $numbers[i], " "; end }
    print "\n"
    $solutions = $solutions + 1
  else
    if k < $numbers.length
      if target_sum >= $numbers[k]
        $flags[k] = true
        find_solutions k+1, target_sum-$numbers[k]
        $flags[k] = false
      end
      find_solutions k+1, target_sum
    end
  end
end

def find_subset_sum(target_sum)
  print "\nNow listing all subsets which sum up to ", target_sum, ":\n"
  $solutions = 0
  (0..$numbers.length()).each { |i| $flags[i] = false }
  find_solutions 0, target_sum
  print "Found ", $solutions, " different solutions.\n"
end

def subset_sum_test(size)
  total = 0
  target_sum = 0
  (0..size).each { |i| $numbers[i] = rand(1000); total += $numbers[i]; print $numbers[i], " " }
  target_sum = total/2
  find_subset_sum target_sum
end

subset_sum_test 25

Comparing this to my other implementations in various languages, this solution is shorter than the Lisp version, and roughly the same length as the VB code I wrote. I'm pretty sure that as I learn more about Ruby I will be able to improve quite a bit on the above naïve code, so it will probably become even shorter.

But even after the first few minutes of coding in this language, I'm taking away the impression that I can produce code which looks a lot cleaner than, say, Perl code. Well, at least cleaner than the Perl code which I usually write ... big grin



When asked for a TWiki account, use your own or the default TWikiGuest account.



to top

You are here: Blog > BlogOnSoftware20060416

r1.2 - 29 Jan 2007 - 21:01 - ClausBrod to top

Blog
This site
RSS

  2017: 12 - 11 - 10
  2016: 10 - 7 - 3
  2015: 11 - 10 - 9 - 4 - 1
  2014: 5
  2013: 9 - 8 - 7 - 6 - 5
  2012: 2 - 10
  2011: 1 - 8 - 9 - 10 - 12
  2010: 11 - 10 - 9 - 4
  2009: 11 - 9 - 8 - 7 -
     6 - 5 - 4 - 3
  2008: 5 - 4 - 3 - 1
  2007: 12 - 8 - 7 - 6 -
     5 - 4 - 3 - 1
  2006: 4 - 3 - 2 - 1
  2005: 12 - 6 - 5 - 4
  2004: 12 - 11 - 10
  C++
  CoCreate Modeling
  COM & .NET
  Java
  Mac
  Lisp
  OpenSource
  Scripting
  Windows
  Stuff
Changes
Index
Search
Maintenance
Impressum
Datenschutzerklärung
Home



Jump:

Copyright © 1999-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback