Ruby implementation of Knuth's algorithm P, generating all trees

alg-p.rb

def algorithm_p n
    a = ")" + "()"*n
    m = 2*n - 1
    loop do
        yield a[1..-1]

        a[m] = ")"
        if a[m-1].chr == ")"
            a[m-1] = "("
            m -= 1
            next
        else
            j = m - 1
            k = 2*n - 1
            while a[j].chr == "("
                a[j] = ")"
                a[k] = "("
                j -= 1
                k -= 2
            end

            if j == 0
                break
            else
                a[j] = "("
                m = 2*n - 1
                next
            end
        end
    end
end

algorithm_p(4){|s| puts s }