Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
from heapq import nsmallest, nlargest
from itertools import product
def findSmallestStd(food, n):
food.sort(reverse=True)
while len(food) % n:
food.append(0)
family_count = len(food) // n
if n == 2:
# optimal
return list(zip(food[:len(food)//2], reversed(food[len(food)//2:])))
else:
# heuristic approach
partition = [[] for _ in range(family_count)]
for food_item in sorted(food, reverse=True):
partition.sort(key=lambda f: sum(f) if len(f) < n else float('inf'))
partition[0].append(food_item)
return local_search(partition, calc_std(partition))
def local_search(partition, best_std, N = 20):
# find indices with smallest and largest sum
families1 = nsmallest(N, partition, key=sum)
families2 = nlargest(N, partition, key=sum)
best_improved_swap = None
for family1, family2 in product(families1, families2):
for index1, index2 in product(range(len(family1)), range(len(family2))):
family1[index1], family2[index2] = family2[index2], family1[index1]
std = calc_std(partition)
if std < best_std:
best_std = std
best_improved_swap = (family1, family2, index1, index2)
family1[index1], family2[index2] = family2[index2], family1[index1]
if best_improved_swap:
family1, family2, index1, index2 = best_improved_swap
family1[index1], family2[index2] = family2[index2], family1[index1]
partition = local_search(partition, best_std)
elif N < 100:
return local_search(partition, best_std, 100)
return partition
def calc_std(partition):
sums = [sum(f) for f in partition]
mean = sum(sums) / len(partition)
return (sum((f - mean)**2 for f in sums) / len(partition))**0.5
if __name__ == "__main__":
with open('codegolfvectoroptimization.txt') as f:
v = [int(line.strip()) for line in f]
results = []
for n in [2, 3, 23]:
food_partition = findSmallestStd(v[:], n)
std = calc_std(food_partition)
results.append(std)
print('STD for n = {0}: {1}'.format(n, std))
print(food_partition)
print('{0} = {1}'.format(' + '.join(map(str,results)), sum(results)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.