From c6c68d95229bc743b79f9f9ed813dfd9cce34df0 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Fri, 14 Mar 2014 22:59:16 +0000 Subject: [PATCH] Use known bound data to refine the search space. --- partition.py | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) diff --git a/partition.py b/partition.py index 18a3a3b..b539d32 100755 --- a/partition.py +++ b/partition.py @@ -3,6 +3,8 @@ import sys, subprocess, math, getopt from fractions import Fraction +import bounds + verbose = False def vprint(*args): # In verbose mode, print diagnostics. @@ -127,12 +129,15 @@ def search(n, m): # Trivial special case. return (m, 1, {(m,):n}, {(m,)*(n/m):m}) best = (0,) + bound, _ = bounds.upper_bound(n, m) for d in xrange(1, n+1): - for k in xrange(m*d/2, int(math.ceil(best[0]*d))-1, -1): + for k in xrange(int(bound*d), int(math.ceil(best[0]*d))-1, -1): result = try_one_minfrag(n, m, k, d) if result is not None: best = (Fraction(k, d), d) + result break + if best == bound: + break # terminate early if we know it's the best answer return best def search_and_report(n, m): -- 2.30.2