Search code examples
rubyarrayssetprefix

clean "prefixes" in a set of arrays?

I was wondering, I've got a Set of Arrays containing something of my own datatype. something looking like:

traces = {[<label1>, <label2>], [<label1>], [<label1>,<label2>,<label3>]}

Now, I would like to have a method that cleans all 'prefix'-existing arrays in the Set, so my new set will be in this example:

traces = {[<label1>,<label2>,<label3>]}

Anybody an idea how to make a clean implementation out of this? I hope there is a neater solution than stepping through traces and a Set new_traces and comparing every array-item several times.

Note: I define Array A is a prefix of Array B iff the first items of Array B are actually the Array A

Solution

  • Not quite the fastest solution, but rather simple:

    s = Set.new([[1,2],[1],[1,2,3]])
s.reject{|prefix|
  s.any?{|array|
    array.length > prefix.length && array[0,prefix.length] == prefix
  }
}
#=>[[1, 2, 3]]