Skip to content

Instantly share code, notes, and snippets.

@weyou weyou/grouping_problem.py
Last active May 26, 2017

Embed
What would you like to do?
grouping_problem
# A group of N integer numbers need to be divided fairly into K subgroups.
# A fair division is that the max of the sums of K subgroups is minimal
def grouping(n, k):
a = sum(n) / k
nums = sorted(n, reverse=True)
groups = []
gsums = []
for _ in range(k):
group = [nums.pop(0)]
groups.append(group)
gsum = group[0]
while True:
gnext_num = 0
gnext_i = -1
for i, num in enumerate(nums):
if gsum + num <= a and num > gnext_num:
gnext_num = num
gnext_i = i
if gnext_i > -1:
gsum += gnext_num
group.append(gnext_num)
nums.pop(gnext_i)
else:
break
gsums.append(gsum)
for num in nums:
i = gsums.index(min(gsums))
groups[i].append(num)
gsums[i] += num
return groups
if __name__ == "__main__":
import random
print(grouping([12, 11, 10, 9, 8, 7, 3, 2], 4))
print(grouping([6, 6, 5, 2, 1, 1], 2))
print(grouping([6, 6, 5, 2, 1, 1], 3))
print(grouping([6, 6, 5, 2, 1, 1], 4))
print(grouping([9, 2, 1], 2))
print(grouping([6, 5, 3, 2, 2], 2))
print(grouping([8, 5, 5, 2, 2, 6], 5))
for i in range(100):
n = random.sample(range(1,100), 7)
print('N =', n)
for k in range(2, 5):
result = grouping(n, k)
print(' K =', k, ": ", result, 'Avg:', sum(n) / k, 'Max: ', max([sum(g) for g in result]))
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.