Skip to content

Instantly share code, notes, and snippets.

@Taiiwo

Taiiwo/README.md

Last active September 27, 2016 21:10
Show Gist options
  • Save Taiiwo/8efc38a2b32604eebf5f491273690ebf to your computer and use it in GitHub Desktop.
Save Taiiwo/8efc38a2b32604eebf5f491273690ebf to your computer and use it in GitHub Desktop.
Download ZIP
Sorts a list of sizes into min number of groups, where each group has a maximum size
Raw
README.md

I wrote this to help me to estimate the number of planks of wood I would need to build some furniture (The measurements of that furniture can still be found in the code). It has many uses. Obviously it can be used for splitting any material of a given length into an array of sizes in an efficient way, but it can also be used for other group sorting problems like fitting groups of people into, busses, or hotel rooms etc.

It's not the fastest solution, it just calculates all possible combinations, nor is it perfectly accurate as it just creates a list of the most efficient groups that can be made in order, but it's a pretty good solution for its application, which only needs to answer the question: How many planks of wood do I need?

Raw
group_sort.py
import itertools
# Gets all combinations of a given array
def all_combinations(array):
for L in range(0, len(array)+1):
for subset in itertools.combinations(array, L):
yield subset
# Returns a group of elements from sizes that most closely sums to, without
# exceeding max
def split(sizes, max):
best_diff = -1
for combination in all_combinations(sizes):
if sum(combination) <= max:
if best_diff == -1 or max - sum(combination) < best_diff:
best_diff = max - sum(combination)
best_combination = combination
return best_combination
# The list of sizes to fit
sizes = [0.71, 1.56, 1.47, 1.32, 0.96, 0.75, 0.75, 0.72, 0.6, 0.6, 0.45, 0.45]
# The max size of the groups to fit them into
max = 2.1
result = []
print("Creating groups of <%s out of %s sizes" % (max, len(sizes)))
# Keep going until there's less than one thing left because, assuming none of
# the sizes exceed the max, the last group doesn't need to be computed, as it
# should fit into the last group regardless. Think of it as the remainder group
while len(sizes) > 1:
# get the best group of the sizes list
combination = split(sizes, max)
# remove the best group from the list so we can calculate the next best
# group
for size in combination:
sizes.remove(size)
# add the best group to the list of groups
result.append(combination)
# repeat until we've run out of things to sort
# Print out our result
for index, group in enumerate(result):
print("Group %s: %s = %s" % (index, group, round(sum(group), 5)))
print("With %s in the remainder group" % sizes)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment