#!/usr/bin/env python3

""" It is well known the C*-algebra of an ordered pair of qubits
    is given by M_2 (x) M_2.  But what about an unordered pair?
    It is easily defined abstractly, by quotienting out action of
    exchanging the two qubits, but what algebra is it?  In [1] it
    is shown that it is in fact M_3 (+) C.  In fact, a formula is
    derived to characterize the C*-algebra of an unorderd n-tuple
    of q-level quantum systems.  This script performs these
    calculation. """

def unordered_ntuple_of_dqudits(n, d):
    """ Calculates the m_1, ..., m_n such that

            M_{m_1} (+) ... (+) M_{m_n}

        is the C*-algebra that models the unordered n-tuples of
        d-level quantum systems.

        >>> unordered_ntuple_of_dqudits(2, 2)
        [3, 1]
        >>> unordered_ntuple_of_dqudits(3, 3)
        [10, 8, 1]
        >>> unordered_ntuple_of_dqudits(5, 2)
        [6, 4, 2]
        >>> unordered_ntuple_of_dqudits(2, 5)
        [15, 10]
        >>> unordered_ntuple_of_dqudits(5, 5)
        [126, 224, 175, 126, 75, 24, 1]
        """
    return [dim_GLd_rep(y, d) for y in young(n, d)]


def dim_GLd_rep(y, d):
    """ Returns the dimension of irreducible representaiton of GL(d)
        corresponding to the Young tableau y. """
    y = tuple(y) + (0,) * (d - len(y))
    if len(y) > d and y[d] > 0: return 0
    num = 1
    den = 1
    for j in range(2, d+1):
        for i in range(1, j):
            num *= y[i-1] - y[j-1] + j - i
            den *= j-i
    return num/den

def young(n, max_height=None):
    """ Iterates over the n-box Young tableaux.  These tableaux correspond
        to partitions of n and irreducible representations of GL(n)
        and Sym(n) on (C^n)^{(x)n}.
    
    >>> list(young(5))
    [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
    >>> list(young(5, max_height=2))
    [[5], [4, 1], [3, 2]]
    >>> [len(tuple(young(n))) for n in range(10)]
    [0, 1, 2, 3, 5, 7, 11, 15, 22, 30]
    """
    return _young(n, n, n if max_height is None else max_height)

def _young(n, w, h):
    """ Helper function to `young` --- returns the n-block Young diagrams
        with maximum width `w` and maximum height `h`. """
    if n == 0: return
    if h == 0: return
    for i in reversed(range(1, min(w, n) + 1)):
        if i == n:
            yield [n]
            continue
        for remainder in _young(n - i, min(w, i), h-1):
            yield [i] + remainder

if __name__ == '__main__':
    import doctest
    doctest.testmod()