David Sletten
4/17/2006 9:34:00 AM
Eli Bendersky wrote:
> Hello all,
>
> How would you code, in the most Rubyish way possible: (1) given an
> array, decide whether it is strictly increasing, and (2) given two
> arrays, decide whether the first is a subsequence of the second.
>
> Here are my trivial implementations:
>
> def increasing_sequence?(seq)
> seq.each_with_index do |x, i|
> return false if i > 0 and seq[i - 1] >= x
> end
>
> return true
> end
>
>
> def is_subsequence_of?(seq, other_seq)
> i = 0
> seq.each do |x|
> while other_seq[i] != x
> i += 1
> return false if (i >= other_seq.length)
> end
> end
>
> return true
> end
>
This doesn't quite work:
irb(main):625:0> is_subsequence_of?([4, 4, 6], [1, 2, 3, 4, 5, 4, 5, 6,
7, 8])
=> true
Basically it optimistically just keeps checking whether any remaining
elements of the first sequence are interspersed among the other
sequence. I don't think this is what you intended.
> I'm wondering if (1) is there a more Rubyish way to implement this ?
> and (2) is there a more efficient way to implement this in pure Ruby ?
As far as is_subsequence_of? goes (I call mine search, which is its name
in Lisp) you need 2 loops, similar to what you have, but with a twist.
The outer loop allows you to backtrack in case of a failure after a
partial match. In Java or C you would numerically index both arrays, but
we don't have to do that in Ruby. However, it's more efficient to remove
that termination test that you have in your inner loop. Instead we can
specify the termination condition at the beginning. But this requires us
to keep track of our index manually in the outer loop. Also, it's
helpful to return the index of the match as a true value. So we get:
def search(a1, a2)
diff = a2.length - a1.length
if diff < 0 then return false
else
0.upto(diff) do |i|
catch :outer do
a1.each_with_index do |elt, j|
throw :outer unless elt == a2[i+j]
end
return i
end
end
return false
end
end
I came up with a more Rubyesque increasing_sequence? (called monotone?
since it works in either direction):
def monotone?(a, test=lambda {|x, y| x < y})
a.inject {|x, y| if test.call(x, y) then y else break end}
end
The default behavior checks for increasing sequences:
irb(main):675:0> monotone?([1, 2, 6])
=> 6
irb(main):676:0> monotone?([1, 2, 6, 4])
=> false
But we can check for decreasing sequences too:
irb(main):677:0> monotone?([1, 2, 6], lambda {|x, y| x > y})
=> false
irb(main):678:0> monotone?([3, 2, 1], lambda {|x, y| x > y})
=> 1
There's probably a simpler way to pass in Comparable.> above, but I
don't know what it is yet. :)
Aloha,
David Sletten