I have a list of suitcases, each suitcase has a name and a weight associated to it. I want to write a function that groups these suitcases in a way together that their weights always forms a multiple of 8 and returns a list of the formed tuples. If there is a suitcase that can not be formed to a multiple of 8ths then that suitcase gets "filled up" with 1s (this should only be the last resort). So for example:

sc1 = suitcase("sc1", 5)
sc2 = suitcase("sc2", 1)
sc3 = suitcase("sc3", 3)
sc4 = suitcase("sc4", 14)
sc5 = suitcase("sc5", 4)
sc6 = suitcase("sc6", 1)
sc7 = suitcase("sc7", 8)
sclist = [sc1,sc2,sc3,sc4,sc5,sc6,sc7]

sorted_tuple = sort_suitcases(sclist)

sorted_tuple = [(sc7),(sc1,sc3),(sc4,sc2,sc6),(sc5,{1,1,1,1})] # this is obviously only one of many possible combinations.
# having only one big tuple would obviously also be a solution

My approach would be looping over each value and loop over each other value left in the list and see if their weight combined is %8, but I feel like this approach would be not very efficient with big data sets. Am I missing something?

CodePudding user response：

1. Partition the suitcases into 8 groups, based on their weight % 8.
2. Pair up members of the groups to make sums that are multiples of 8: 1 & 7, 2 & 6, 3 & 5, 4 & itself.
3. Deal with those that couldn't be paired off (larger groups & filling-up)