# Code to pick buckets for a list of value

In my current project, I came across a scenario where there will be two sorted list of Decimal values. Let's call them bucket_list and value_list

1. Where bucket_list represents the sum of one or more elements from the value_list
2. value_list may have duplicate values
3. Every element in value_list should be picked only once (duplicate values are considered different elements)
4. In the end, all elements in bucket_list will have one or more element from value_list and no elements in value_list will be left without a mapping to bucket_list

After a lot of searches, I wrote the code with backtracking and greedy(I think). Below is the part of code that handles the part of the problem.

    class FindBucketMap(object):
@classmethod
def create_map_list(cls, bucket_list: list, value_list: list, bucket_map_list: list, i: int = 0):
"""
Backtracking code to find possible bucket and value pair
:param bucket_list: List of bucket values
:param value_list: List of values to map to bucket
:param bucket_map_list: List will be updated with the mapping of values from bucket_list to value_list
:param i:
:return:
"""
if i >= len(bucket_list) or len(value_list) == 0:
if i >= len(bucket_list) and len(value_list) == 0:
return True
else:
return False
bucket_map_prospect_list = []
bucket_value = bucket_list[i]
cls.create_map(bucket_value, value_list, [], bucket_map_prospect_list)
if len(bucket_map_prospect_list) == 0:
return False
for bucket_map_prospect in bucket_map_prospect_list:
temp_list = list(value_list)
for x in bucket_map_prospect:
temp_list.remove(x)
if cls.create_map_list(bucket_list, temp_list, bucket_map_list, i + 1):
bucket_map_list.append({"bucket": bucket_value, "split": bucket_map_prospect})
return True

@classmethod
def create_map(cls, value: Decimal, value_list: list, cur_list: list, map_list: list, i: int = 0):
"""
Greedy code to find list of values that matches a sum
:param value:  Expected Sum
:param value_list: Possible values
:param cur_list: Processed values
:param map_list: List contains the possible combinations
:param i:
:return:
"""
if value == Decimal(0):
map_list.append(cur_list)
return
if value < Decimal(0):
return
while i < len(value_list):
if value < value_list[i]:
return
cls.create_map(value - value_list[i], value_list, cur_list + [value_list[i]], map_list, i + 1)
i += 1


Please give reviews on the approach and the code.

EDIT 1:

For a large test case ( len(bucket_list) > 50 and len(value_list) > 1000 ), the program almost never ends. So I changed the code to the following:

    class FindBucketMap(object):
@classmethod
def create_map_list(cls, bucket_list: list, value_list: list, i: int = 0):
if i >= len(bucket_list):
return True
return cls.create_map(bucket_list[i], bucket_list, value_list, [], i)

@classmethod
def create_map(cls, value: int, bucket_list: list, value_list: list, cur_list: list, i: int, j: int = 0):
if value == 0:
temp_list = list(value_list)
for x in cur_list:
temp_list.remove(x)
print(i, bucket_list[i], cur_list)
result = cls.create_map_list(bucket_list, temp_list, i + 1)
if result is True:
return [{"value": bucket_list[i], "split": cur_list}]
elif isinstance(result, list):
return result + [{"value": bucket_list[i], "split": cur_list}]
else:
return False
if len(value_list) == 0 or value < Decimal(0):
return False
while j < len(value_list):
if value < value_list[j]:
return False
result = cls.create_map(value - value_list[j], bucket_list, value_list, cur_list + [value_list[j]], i,
j + 1)
if isinstance(result, list):
return result
j += 1
return False


This is faster than the first but still not fast enough.

Just a couple ways to shorten your code

This code

if i >= len(bucket_list) or len(value_list) == 0:
if i >= len(bucket_list) and len(value_list) == 0:
return True
else:
return False


can be written like this:

if i >= len(bucket_list) or not value_list:
return i >= len(bucket_list) and not value_list


This allows you to return the boolean value this expression would evaluate too, and not value_list means the length of value_list is 0, or empty. I changed other occurances of this in your code as well.

This code

for x in bucket_map_prospect:
temp_list.remove(x)


can be written like this:

temp_list.remove(x for x in bucket_map_prospect)


If you're going to use type hints, you might as well hint at what the method is returning. From this

def function(...):


to this

def function(...) -> bool/int/etc:


You'll see what I mean when you look at the updated code.

Updated Code

class FindBucketMap(object):
"""
Class Docstring
"""
@classmethod
def create_map_list(cls, bucket_list: list, value_list: list, bucket_map_list: list, i: int = 0) -> bool:
"""
Backtracking code to find possible bucket and value pair
:param bucket_list: List of bucket values
:param value_list: List of values to map to bucket
:param bucket_map_list: List will be updated with the mapping of values from bucket_list to value_list
:param i:
:return:
"""
if i >= len(bucket_list) or not value_list:
return i >= len(bucket_list) and not value_list

bucket_map_prospect_list = []
bucket_value = bucket_list[i]
cls.create_map(bucket_value, value_list, [], bucket_map_prospect_list)

if not bucket_map_prospect_list:
return False

for bucket_map_prospect in bucket_map_prospect_list:
temp_list = list(value_list)
temp_list.remove(x for x in bucket_map_prospect)
if cls.create_map_list(bucket_list, temp_list, bucket_map_list, i + 1):
bucket_map_list.append({"bucket": bucket_value, "split": bucket_map_prospect})
return True

@classmethod
def create_map(cls, value: Decimal, value_list: list, cur_list: list, map_list: list, i: int = 0) -> None:
"""
Greedy code to find list of values that matches a sum
:param value:  Expected Sum
:param value_list: Possible values
:param cur_list: Processed values
:param map_list: List contains the possible combinations
:param i:
:return:
"""
if value == Decimal(0):
map_list.append(cur_list)
return
if value < Decimal(0):
return
while i < len(value_list):
if value < value_list[i]:
return
cls.create_map(value - value_list[i], value_list, cur_list + [value_list[i]], map_list, i + 1)
i += 1