5
\$\begingroup\$

Solved the below problem. Would love to hear your feedback, especially on performance improvements (granted, the solution should remain recursive).

Especially concerned about the obj.include? elem check I had to add to prevent duplicates. Don't know a better way to do without it.

# Implement an algorithm to print all valid (e.g., properly 
# opened and closed) combinations of n-pairs of parentheses.
# EXAMPLE
# Input: 3
# Output: ((())), (()()), (())(), ()(()), ()()()

def brackets(n)
  return ["()"] if n == 1

  brackets(n-1).each_with_object([]) do |p, obj|
    for i in 0..p.length
      # stuff the "()" in every possible position within 'p'
      elem = p.dup.insert(i, "()")
      obj << elem unless obj.include? elem
    end
  end
end
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

It's a nice solution!

One thing that might speed things up a little would be to use a Set; no need for the include? then. Just call to_a on it at the end (or don't, and return a Set - still fits the task).

Also, I'd use p.length.times { |i| ... } instead of a for loop, and make a couple of variable names a little more descriptive (p, for instance, is not a very descriptive name).

require 'set'

def brackets(n)
  return ["()"] if n == 1

  brackets(n-1).each_with_object(Set.new) do |str, set|
    str.length.times do |i|
      set << str.dup.insert(i, "()")
    end
  end.to_a
end

Or, without converting to an array:

def brackets(n)
  return Set.new(["()"]) if n == 1

  brackets(n-1).each_with_object(Set.new) do |str, set|
    str.length.times do |i|
      set << str.dup.insert(i, "()")
    end
  end
end

brackets(3) # => #<Set: {"()()()", "(())()", "()(())", "(()())", "((()))"}>

Might also be nice to avoid the duplicated "()" string. You could make it an argument, so the method can be used for other "pairs", e.g:

def brackets(n, pair = "()")
  return Set.new([pair]) if n == 1

  brackets(n-1, pair).each_with_object(Set.new) do |str, set|
    str.length.times do |i|
      set << str.dup.insert(i, pair)
    end
  end
end

brackets(3, "<>") # => #<Set: {"<><><>", "<<>><>", "<><<>>", "<<><>>", "<<<>>>"}>

Or you can simply make it a constant, like SINGLE_PAIR = "()".freeze.

\$\endgroup\$
1
  • \$\begingroup\$ Ah, excellent suggestion on the use of a Set! Thanks! \$\endgroup\$ Apr 18, 2017 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.