import itertools


def AllBipartitions(data, comblength=None):
    """Given a set, finds all possilbe bipartitions.

    If optional 'comblength=None', it will return all bipartitions of
    all sizes. If 'comblength' is an integer, it will return all bipartitions
    in which one of the subsets has size N1 = comblength and complementary
    has size N2 = len(data) - comblength.

    Parameters
    ----------
    data : array_like
        A list, tuple or array containing data.
    comblength : integer, optional
        The size of one of the two complementary subsets.

    Returns
    -------
    result : list
        A list with all possible bipartitions of the elements in 'data'.

    See Also
    --------
    AllCombinations, AllPermutations

    Examples
    --------
    >>> AllBipartitions((1,2,3,4))
    >>> [((1,), (2, 3, 4)),
        ((2,), (1, 3, 4)),
        ((3,), (1, 2, 4)),
        ((4,), (1, 2, 3)),
        ((1, 2), (3, 4)),
        ((1, 3), (2, 4)),
        ((1, 4), (2, 3))]
    >>>
    >>> AllBipartitions(('s','p','a','m'))
    >>> [(('s',), ('a', 'p', 'm')),
        (('p',), ('a', 's', 'm')),
        (('a',), ('p', 's', 'm')),
        (('m',), ('a', 'p', 's')),
        (('s', 'p'), ('a', 'm')),
        (('s', 'a'), ('p', 'm')),
        (('s', 'm'), ('a', 'p'))]
    """
    # 0) PREPARE FOR CALCULATIONS
    Ndata = len(data)
    iseven = Ndata % 2 == 0
    Nmax = Ndata // 2
    setdata = set(data)

    # Security check, avoid confusing comblength=0 with None
    if comblength == 0:
        raise ValueError( "'comblength' out of range, please make sure 0 < comblength < len(data)." )

    ########################################################################
    # 1) DEFINE THE TWO FUNCTIONS THAT WILL DO THE ACTUAL JOB
    def AllBipartitionsAllSizes(data):
        """Given a dataset, it finds all bipartitions of all sizes.
        """
        # 1) FIND ALL THE COMBINATIONS UP TO LENGTH < len(data)/2
        bipartitions = []
        for n in range(1, Nmax):
            # 1.1) Find all combinations of given size out of dataset
            combinations = [c for c in itertools.combinations(data, n)]
            # 1.2) Sort and find complementary sets
            for comb in combinations:
                complementary = tuple(setdata - set(comb))
                bipartitions.append((comb, complementary))

        # 2) FIND AND SORT THE BIPARTITIONS OF SIZE Nmax
        # 2.1) Find all combinations of size Nmax
        combinations = [c for c in itertools.combinations(data, Nmax)]
        # 2.2) Sort and find complementary sets
        ncombs = len(combinations)
        # Ignore repeated combinations if both subsets are of size = Nmax
        if iseven: ncombs = ncombs // 2

        for i in range(ncombs):
            comb = combinations[i]
            combset = set(comb)
            complementary = setdata - combset
            bipartitions.append((comb, tuple(complementary)))

        return bipartitions

    def AllBipartitionsGivenSize(data, comblength):
        """Given a dataset, finds all bipartitions in which one of the
        subsets is of size 'comblength'. The size of the complementary
        subset is N - 'comblength', where N is the size of the data.
        """
        # 0) SECURITY CHECKS
        comblength = int(comblength)
        if (comblength < 1 or comblength >= Ndata):
            raise ValueError( "'comblength' out of range, please make sure 0 < comblength < len(data)." )

        # 1) FIND ALL THE COMBINATIONS OF SIZE 'comblength'
        combinations = [c for c in itertools.combinations(data, comblength)]

        # 2) SORT AND FIND THE COMPLEMENTARY SETS
        bipartitions = []

        # If size of set is even, and we are looking for bipartitions of size
        # Nmax, then we need to remove repeated combinations
        if iseven and comblength == Nmax:
            ncombs = len(combinations)
            for i in range(ncombs // 2):
                comb = combinations[i]
                combset = set(comb)
                complementary = setdata - combset
                bipartitions.append((comb, tuple(complementary)))

        # For any other case, bipartitions are found as usual
        else:
            for comb in combinations:
                complementary = tuple(setdata - set(comb))
                bipartitions.append((comb, complementary))

        return bipartitions

    ########################################################################
    # 2) DO THE JOB
    if comblength:
        result = AllBipartitionsGivenSize(data, comblength)
    else:
        result = AllBipartitionsAllSizes(data)

    return result