Created
February 23, 2018 20:05
Star
You must be signed in to star a gist
Finding permutations with disjoint partial sums
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/python3 | |
def flatten(index_map): | |
flat = [0] * len(index_map) | |
for key in index_map.keys(): | |
flat[index_map[key]] = key | |
return flat | |
def emit_solution(x, partial_solution): | |
total_sum = x*(x+1)//2 | |
print([flatten(row) + [total_sum - sum(row.keys())] for row in partial_solution]) | |
def search(x, partial_solution, partial_sum): | |
h = x//2 + 1 | |
if partial_sum == x*(x+1)//2: | |
emit_solution(x, partial_solution) | |
else: | |
delta = [0] * h | |
# Optimised for early return | |
for i in range(h): | |
delta[i] = partial_sum - sum(partial_solution[i]) | |
if delta[i] > x: | |
# No valid value we can append to partial_solution[i] avoids repetition | |
return | |
for i in range(h): | |
# Check that we're not going to get a non-permutation | |
if delta[i] in partial_solution[i]: | |
continue | |
# Try it and then undo the change | |
partial_solution[i][delta[i]] = len(partial_solution[i]) | |
search(x, partial_solution, partial_sum + 1) | |
partial_solution[i].pop(delta[i]) | |
# Optimise: only insert the entire partial sum as the first value in an | |
# empty permutation in the first empty permutation of partial_solution | |
if delta[i] == partial_sum: | |
break | |
def brute_force(x): | |
h = x//2 + 1 | |
partial_solution = [dict() for _ in range(h)] | |
search(x, partial_solution, 1) | |
brute_force(2) | |
brute_force(4) | |
brute_force(6) | |
brute_force(8) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
A further optimisation would be to track the values of
sum(partial_solution[i])
rather than to keep recalculating them.