Instantly share code, notes, and snippets.

# dhermes/advancing_front.py Last active Sep 17, 2018

 import itertools import operator def is_canonical(n_tuple): # |b1| <= |bn| ==> -b1 <= bn ==> b1 + bn >= 0 return n_tuple[-1] + n_tuple[0] >= 0 def beta_values_to_p(n_tuple, n): # beta1 = -1 - p1 ==> p1 = -1 - beta1 p = [None] * n p[0] = -1 - n_tuple[0] for i in xrange(1, n): p[i] = n_tuple[i] - n_tuple[i - 1] - 1 return p def advance_tuple(n_tuple, n): first_update = n_tuple[:] for tuple_index in xrange(n): first_update[tuple_index] -= 1 yield first_update for index in xrange(1, n): next_update = n_tuple[:] for tuple_index in xrange(index, n): next_update[tuple_index] += 1 yield next_update def advance_stage(stage, n): new_stage = set() for n_tuple in stage: for new_tuple in advance_tuple(n_tuple, n): new_stage.add(tuple(new_tuple)) return sorted(map(list, new_stage), reverse=True) def compute_values(curr_stage, stage, sd, sd_plus_one): print('Stage: %d' % (curr_stage,)) print('-' * 40) for n_tuple in stage: sd_val = sd(n_tuple) sd_plus_one_val = sd_plus_one(n_tuple) message = '%20s -> %s' % (n_tuple, sd_plus_one_val) if sd_val == 0: if is_canonical(n_tuple): print(message) def advance_front(n, sd, sd_plus_one, num_stages=3): stage = [range(-1, -1 + n)] compute_values(0, stage, sd, sd_plus_one) for curr_stage in xrange(num_stages): stage = advance_stage(stage, n) compute_values(curr_stage + 1, stage, sd, sd_plus_one) def make_sj(j): def sj(n_tuple): result = 0 for val_tuple in itertools.combinations(n_tuple, j): result += reduce(operator.mul, val_tuple, 1) return result return sj if __name__ == '__main__': s1 = make_sj(1) s2 = make_sj(2) print('') advance_front(5, s1, s2, num_stages=11)