Skip to content

Instantly share code, notes, and snippets.

@pjt33
Created February 23, 2018 20:05
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save pjt33/e2018001ce0557abdd878b37cda7695d to your computer and use it in GitHub Desktop.
Finding permutations with disjoint partial sums
#!/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)
@pjt33
Copy link
Author

pjt33 commented Feb 23, 2018

A further optimisation would be to track the values of sum(partial_solution[i]) rather than to keep recalculating them.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment