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 ...

---

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

---