Semergence

I recently had to sort by multiple conditions in Ruby, and had a hard time coming up with the Ruby way to do this. The Ruby Docs didn’t have what I was looking for, either.

Thankfully, #ruby-lang was very helpful (and confirmed that the docs were lacking here).

Let’s say you want to sort this array of arrays:

a = [[1,2,3],[1,0,2],[2,3,2]]

and you want to sort by both the 0 and 1 indexes of the inner arrays.

You can write this:

a.sort_by{|e| [e[0],e[1]]}

You will get this:

[[1,0,2],[1,2,3],[2,3,2]]

The sort_by method is used when it’s costly to do the comparison itself (for instance, if you need to sort File objects, which are costly to create during a normal call to sort).

sort_by creates another enumeration of keys, one for every element in your array to be sorted. In the above example, we are relying on the fact that Array implements the <&eq;> method. So we are creating a new array which contains the multiple elements corresponding to our multiple conditions.

Note that this trick of creating an array of the sortable values will work just fine in sort.

Well, thanks to the many people (here and here) that provided their versions of an erlang way to calculate combinations, I’ve really begun to open my mind to how to think functionally.

To help me understand what is going on, I’ve converted the basic idea into a Ruby version of calculation combinations. This uses recursion like the erlang versions do.

class Array
  def head_tail
    [self.first, self.tail]
  end

  def tail
    self[1,self.size-1]
  end
end

def combos(list)
  return [[]] if list.empty?
  h, t = list.head_tail
  t_combos = combos(t)
  t_combos.inject([]) {|memo, obj| memo << [h] + obj} + t_combos
end

c = combos([1,2,3,4])
require 'pp'
pp c

As you can see, I added a bit of erlangism to the Array class, by adding a method to get the head and tail of an array.

Let’s run through this.

On the first call to combos([1,2,3,4]) we jump over the first line (the exit in our recursion). We generate the head and tail, which in this case is 1 and [2,3,4] respectively. We immediately begin our recursion by saying, “Get me all the combinations for the tail, which is essentially everything but the head.” Then, for each of those combinations, we append the head (again, here it’s 1). Finally, we add all of the rest of the combinations and return the array of arrays.

Another way to explain it might be:

1. H = Remove an element from the list.
2. T = The rest of the list.
3. C = Calculate the combinations of T (recursion happens here).
4. C2 = For each combination in C, generate a new combination by appending H.
5. return C2 + C

I recently had to calculate all possible combinations of a set. I needed to calculate combinations of 1..N size, where N is the size of the original set of things. Order inside of the resulting combinations did not matter to me, as I am treating the combinations as true sets.

For example, given the set [A,B,C], I needed to calculate the following combinations:

• []
• [A]
• [B]
• [C]
• [AB]
• [AC]
• [BC]
• [ABC]

It dawned on me that a cool way to generate the combinations was to treat the sets (the original set and the resulting combination sets) as bit strings. If the bit corresponding to the member is on, I include the member in the combination.

To explain, I start with the set [A,B,C]. I create a number that has three bits, all on, one for each member of the set. I therefore have the binary number 111 matching [A,B,C]. 111 happens to be 7 in decimal, which is one less than the total number of combinations I require.

Starting with zero, I loop up and including seven (for a total of eight iterations, once for each combo that I want). I convert each iteration count to a binary string, which will give me which bits are on for this combination.

For example, here’s the ruby code:

original_set = [:A, :B, :C]
combinations = []

def create_combo(bit_string, original_set)
  combo = []
  bit_string.split(//).each_with_index do |bit, i|
    combo << original_set[i] if bit == "1"
  end
  combo
end

(2**original_set.size).times do |i|
  bit_string = sprintf("%03b", i)
  combinations << create_combo(bit_string, original_set)
end

require 'pp'
pp combinations

This will print out:

[[], [:C], [:B], [:B, :C], [:A], [:A, :C], [:A, :B], [:A, :B, :C]]

Neat, huh?

I’m sure you can speed this up by checking each bit in the iteration count instead of first converting to a bit string.

…Rubyists tend to function in evangelistic/defensive mode continuously compared to the Java tradition of intense self-criticism…

Found in In Relation To…

Google’s Summer of Code is sponsoring a Framework for ETL and Data mining operations in Ruby.

Hmm… sounds a lot like ActiveWarehouse ETL, which is a Ruby library for ETL. ActiveWarehouse-ETL is already in progress and well on its way.

Here’s the whole list of Ruby projects sponsored by Summer of Code.

I was looking for a way to create combinations of things in Ruby and I found an article by Uncle Bob detailing his attempt at writing a combination generator in Ruby. I modified it slightly to use an array of items, instead of simple indexes.

require 'pp'

def choose(n, k)
  return [[]] if n.nil? || n.empty? && k == 0
  return [] if n.nil? || n.empty? && k > 0
  return [[]] if n.size > 0 && k == 0
  c2 = n.clone
  c2.pop
  new_element = n.clone.pop
  choose(c2, k) + append_all(choose(c2, k-1), new_element)
end

def append_all(lists, element)
  lists.map { |l| l << element }
end

all = [:a, :b, :c, :d]

pp choose(all,3)

The above code prints out:

[[:a, :b, :c], [:a, :b, :d], [:a, :c, :d], [:b, :c, :d]]

If you don’t want these types of combinations, there is a Ruby library for calculating Permutations which will give you all the different permutations, or orderings, of a set of things.

The more I work with Ubuntu, the more I think it’s a very good desktop, but not a good development machine. For instance, you can install Ruby 1.8.4 from the package management system, but not 1.8.5 (or 1.8.6 which is now the latest). So you’re stuck compiling ruby on your own.

Usually that’s not too big of a deal. However, for some reason, the default way of compiling Ruby from source on Ubuntu leaves out the installation of OpenSSL support. I had the development openssl libraries package installed, so that wasn’t it. I didn’t see any errors in the configure process or during compilation.

Turns out, to get OpenSSL to compile and install with Ruby on Ubuntu, you need to follow these steps *after you’ve installed ruby*:

cd ruby_src_dir/ext/openssl
ruby extconf.rb
make
make install

Success!

That seems a bit harder than it should be, huh?

Resources on Rails highlights some of the new exciting changes to appear in Rails 1.2. The most exciting is ActiveResource, which CRUDifies models as HTTP resources. Go REST!

ActiveRDF: object-oriented RDF in Ruby is a paper submitted to Scripting for the Semantic Web 2006. Inside, the authors discuss the challenges and successes with using RDF as a storage backend for applications, much in the same way that RDBMS are currently used. Scripting languages, such as Ruby, offer the best chance for RDF integration, because RDF is so flexible, dynamic, and often untyped. Ruby, because it is so dynamic (you can easily add methods to classes, for instance), is a good way to see where the intersection between an OO scripting language and semantic web technologies mix.

I’d like to see integration with transactions, plus explicit support for Redland’s contexts. ActiceRDF is a great step forward in learning how deep RDF should go in the application stack.

ActiveRDF is a ORM type product for Ruby that maps Ruby objects to RDF stores.

It’s a very new project, so examples and downloads are lacking. However, apparently it has support for pluggable storage engines. The next step would be to see if I can plug this into Oracle 10g’s RDF store.

Of course, the real value here is if ActiveRDF supports inferencing. Otherwise, it’s a cumbersome ORM product, imho.