Help me tackle this challenging math/programming problem from a contest.

November 20, 2012 11:30 PM

Help me tackle this challenging math/programming problem from a contest.

I was looking at some problems from an old programming contest and this one struck me. Say you're given two numbers, a and z. What you have to do is output every possible partition of a into z coprime numbers, with the numbers within the partitions in non-decreasing order and the partitions themselves in ascending order (if a group of numbers is coprime, then the gcd of any two of them is 1). Order between the partitions is like alphabetic order, but with numbers, so for example if a=40 and z=6, then you would output 1 1 1 1 1 35 first, then 1 1 1 1 5 31, then 1 1 1 1 7 29 and so on. For a=8 and z=3, you would just have the partitions 1 1 6, then 1 2 5, and finally 1 3 4. You can see the first partition will always begin with z-1 ones and end with the number a-z-1. I'm pretty much at a total loss for any kind of general solution though...

posted by bookman117 to grab bag (6 answers total)

I'm typing on my phone and it's just before bed time so this is the brute force solution, but probably not the optimal solution (though you can increase it greatly using memorization).

This seems like a recursive problem to me. That is, if function f(a, z) solves the problem, it would do something like this:

f(a, z, primes = empty list) returns list of coprime partitions as described {
for each number i between 1 and a {
if i is coprime with all numbers in primes {
partial result = f(a-I, z-1, primes.append(i))
for r in partial result {
add result r. append (i)
}
}
}
sort results list
return results list
}

Three things are left to do, but they are relatively simple:

A. How to tell if i is a coprime with numbers in a given list.
B. How to sort the results list as described.
C. How to optimize, including memorization, sorting at the end, or just better algorithms.
posted by ethidda at 12:07 AM on November 21, 2012

Not sure how to efficiently determine coprimes, but I think you can generate the solutions recursively like this (python)

def partition(n, buckets):
	if buckets == 1:
		yield [n]
	elif n >= buckets:
		for i in range(1, n):
			for rest in partition(n - i, buckets - 1):
				yield [i] + rest

def solutions(n, buckets):
	return filter(all_coprime, partition(n, buckets))

This gives me these for 8, 3:
[1, 1, 6]
[1, 2, 5]
[1, 3, 4]
[1, 4, 3]
[1, 5, 2]
[1, 6, 1]
[2, 1, 5]
[2, 5, 1]
[3, 1, 4]
[3, 4, 1]
[4, 1, 3]
[4, 3, 1]
[5, 1, 2]
[5, 2, 1]
[6, 1, 1]
posted by Unexpected Indent at 12:24 AM on November 21, 2012

Note that it's easy to generate all possible co-prime pairs of numbers (see the wikipedia page) which is probably the first step to an efficient solution to this problem.
posted by pharm at 2:38 AM on November 21, 2012

Seems to me that the sorting requirement is going to cut down the number of candidates pretty quick, via a kind of combinatorial implosion effect; Unexpected Indent's list of 15 solutions is reduced to the required 3 if only the sorted variants are selected, and that's with only 3 partitions.

So I'd start with an algorithm designed to generate the partitionings in an inherently sorted order, then find a good place within it to add logic to filter for the coprime property. If the first pair of numbers tested for coprimeness at each step were the ones most recently modified by the partitioning generator, then most of the time I'd expect the filter to reject candidate partitionings with very few tests each.
posted by flabdablet at 6:16 AM on November 21, 2012

I took Unexpected Indent's solution and added the missing pieces:

from fractions import gcd
import sys

def partition(n, buckets, min=1):
    if n < min:
        return
    if buckets == 1:
        yield [n]
    elif n >= buckets:
        for i in range(min, n):
            for rest in partition(n - i, buckets - 1, i):
                yield [i] + rest

def all_coprime(values):
    for i in range(len(values)):
        for j in range(i+1, len(values)):
            if gcd(values[i], values[j]) > 1:
                return False
    return True
                
def solutions(n, buckets):
    return filter(all_coprime, partition(n, buckets))

def main():
    n = int(sys.argv[1])
    buckets = int(sys.argv[2])
    for sol in solutions(n, buckets):
        print sol

main()

I added a bit to the partition() function to only generate the increasing-order partitions (and it already generated the partitions themselves in the correct order). The coprime check is just brute-force, though, and there is certainly a faster way to do that, if needed. Only adding elements to a growing partition that are coprime with the values already included would probably be much more efficient. There are probably smarter ways to generate the partitions (avoiding lots of "dead ends") as well.
posted by whatnotever at 7:50 AM on November 21, 2012 [1 favorite]

... and after some improvements (purely for efficiency):

from fractions import gcd
import sys

coprimes = []

def partition(n, buckets, allowed):
    global coprimes

    if buckets == 1:  # Have to include n at this point
        if n in allowed:
            yield [n]
        return

    for i in allowed:
        # Prune remaining search if no solution is possible
        if i*buckets > n:
            return
        # Remove values that can't be used any more if we include i
        newallowed = [ x for x in allowed if ((i <= x <= n-i) and coprimes[i][x]) ]
        for rest in partition(n - i, buckets - 1, newallowed):
            yield [i] + rest

def main():
    n = int(sys.argv[1])
    buckets = int(sys.argv[2])

    # Precalculate GCDs
    global coprimes
    for i in range(n+1):
        coprimes.append([False]*(n+1))
        for j in range(i,n+1):
            coprimes[i][j] = (gcd(i,j) == 1)
            
    for sol in partition(n, buckets, allowed=range(1,n+1)):
        print sol

main()

This does what I described above, maintaining a list of values that are still coprime with all earlier values in order to avoid a lot of dead ends. It also removes values that cannot be used due to being less than a value chosen already (i) or more than the amount that remains (n-i). On top of that, it prunes further by stopping whenever no solution can exist because the remaining choices would have to sum to more than n. With any sort of branching, recursive algorithm, pruning is really important. Any time you can prove that a given branch will produce no solutions, you can prune it and save time.

This version also precalculates GCDs to avoid computing the same results over and over. That part could be optimized as well, though it's fast enough for n < 2000 or so.

Overall, one of the best ways to improve an algorithm's efficiency is to avoid redundant or unnecessary work. The improvements in this version do exactly that, and they reduce the runtime immensely for harder instances.
posted by whatnotever at 10:22 AM on November 21, 2012