Independent test of grid factoring methods.

[markkness]

To address #258, we are making changes to allow 1 values in grid_shape. Previously, we had two methods for computing the factors, I think one slow but simpler, and one fast and more subtle. Only the second one of these is surviving the refactor for this, as the first is effectively unused code. But, the deprecated method being removed might be useful as an independent test of the factorization method that we do use. This deprecated method proved difficult to adapt to allowing the 1 values, which also argued for its removal.

But in case this alternate method is later useful for testing, I note the code used here, so it is not lost track of.

def test_both_methods(self):
    """
    Do the two methods of computing the multiplicative partitions agree?
    """
    for s in [2, 3]:
        for n in range(2, 512):
            self.assertEqual(utils.mult_partitions(n, s),
                             utils.create_factors(n, s))

def divisors(n):
    i = 2
    while i<n:
        if n % i == 0:
            yield i
        i += 1

def multi_for(iterables):
    if not iterables:
        yield ()
    else:
        for item in iterables[0]:
            for rest_tuple in multi_for(iterables[1:]):
                yield (item,) + rest_tuple

def create_factors(n, size=2):
    divs = list(divisors(n))
    factors = []
    for indices in multi_for( [range(p) for p in size*[len(divs)]] ):
        total = 1
        for i in indices:
            total = total*divs[i]
        if n == total:
            factor = [divs[i] for i in indices]
            factor.sort()
            factor = tuple(factor)
            if factor not in factors:
                factors.append(factor)
    return factors

def divisors_minmax(n, dmin, dmax):
    """Find the divisors of n in the interval (dmin,dmax]."""
    i = dmin+1
    while i<=dmax:
        if n % i == 0:
            yield i
        i += 1

def mult_partitions(n, s):
    """Compute the multiplicative partitions of n of size s

    >>> mult_partitions(52,3)
    [(2, 2, 13)]
    >>> mult_partitions(52,2)
    [(2, 26), (4, 13)]
    """
    return [tuple(flatten(p)) for p in mult_partitions_recurs(n,s)]

def mult_partitions_recurs(n, s, pd=1):
    if s == 1:
        return [n]
    divs = divisors_minmax(n, pd, int(sqrt(n)))
    fs = []
    for d in divs:
        fs.extend([(d,f) for f in mult_partitions_recurs(n/d, s-1, pd)])
        pd = d
    return fs