# Author: Peter Luschny, Mar 14 2024


'''AlgoP
Enumerate nested parentheses.
Implements Algorithm P from Knuth's the Art of Computer Programming,
(TAOCP, vol. 4A, p. 443).

Usage: python AlgoP.py number
'''

def visit(a):
    p = "".join(a)[1:]
    b = p.replace(")", "0").replace("(", "1")
    print(p, b, int(b, 2))


def AlgoP(k):
    ''' Prints all sets of nested parentheses of order k'''
    n = k        # number of parens
    m = 2*n - 1  # 'index value'

    print(f"-- {n} --")

    if n == 0: visit(['.', '0'])   # P0 algorithm requires n >= 2
    if n == 1: visit(['.', '(', ')'])
    if n <= 1: return

    p = [')' for _ in range(m + 2)]  # P1 initialize
    for k in range(1, n + 1):
        p[2*k - 1] = '('

    while True:
        visit(p)               # P2 visit step

        p[m] = ')'             # P3 easy case
        if p[m - 1] == ')':
            p[m - 1] = '('
            m -= 1
            continue

        j = m - 1              # P4 find j
        k = 2*n - 1
        while p[j] == '(':     # almost always short
            p[j] = ')'
            p[k] = '('
            j -= 1
            k -= 2

        if j == 0:
            return      # P5 increase a_j

        p[j] = '('
        m = 2*n - 1


# =================================================================

'''AlgoU
Unrank a string of nested parentheses.
Implements Algorithm U from Knuth's the Art of Computer Programming,
(TAOCP, vol. 4A).

Usage: python AlgoU.py number
'''

def AlgoU(n, N):
    '''Precondition: 1 <= N <= CatalanNumber(n).'''

    q = n               # U1 initialize
    m = p = c = 1
    a = ['0' for _ in range(2*n + 1)]

    while p < n:
        p = p + 1
        c = ((4 * p - 2) * c) // (p + 1)

    while True:
        if q == 0:       # U2 Done?
            visit(a)
            return

        cc = ((q + 1) * (q - p) * c) // ((q + p) * (q - p + 1))
        if N <= cc:      # U3 Go up
            q = q - 1
            c = cc
            a[m] = ')'
            m = m + 1
            continue

        p = p - 1        # U4 Go left
        c = c - cc
        N = N - cc
        a[m] = '('
        m = m + 1


# =============================================================================

# This is an update of Indranil Ghosh's Python program for computing A063171.
# Although the general construction plan was adhered to, some of the details
# were massively changed. No library functions are used except for a cache.
# The update is from Python 2.7.11 to Python 3.11.6. - Peter Luschny, Mar 13 2024

from functools import cache

@cache
def a000108(n: int):
    if n < 2:
        return 1
    return (a000108(n - 1) * (4*n - 2)) // (n + 1)


@cache
def a014137(n: int):
    if n == 0:
        return 1
    return a000108(n) + a014137(n - 1)


def a072643(n: int):
    if n < 2:
        return n
    j = 0
    while n + 1 > a014137(j):
        j += 1
    return j


@cache
def a009766(n: int):
    if n == 0:
        return [1]
    row = a009766(n - 1) + [0]
    for k in range(1, n + 1):
        row[k] += row[k - 1]
    return row


def CatalanUnRank(n: int, rr: int):
    r = a000108(n) - (rr + 1)
    a = lo = 0
    t = n
    y = n - 1
    while y >= 0:
        m = a009766(t)[y]
        a <<= 1
        if r < (lo + m):
            y -= 1
            a += 1
        else:
            lo += m
            t -= 1
    return a << t


def a014486(n: int):
    if n == 0:
        return 0
    a = a072643(n)
    return CatalanUnRank(a, n - a014137(a - 1))


def a063171(n: int):
    return int(bin(a014486(n))[2:])



if __name__ == '__main__':

    from math import comb as binomial

    print("\nIndranil Ghosh's implementation\n")
    print([a063171(n) for n in range(65)])

    print("\nAlgorithm P\n")
    for n in range(5): AlgoP(n)

    print("\nAlgorithm U\n")
    for n in range(2, 6):
        C = binomial(2*n, n) // (n + 1)
        Test = [1, n, C // 2, (3*C) // 4, C]
        for N in Test: AlgoU(n, min(C, max(1, N)))

    print("\nDemo\n")
    print("Compute the millionth iteration of 15 nested pairs of parentheses.")

    AlgoU(15, 10**6)