Code to pick buckets for a list of value

Question

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.

Answer 1

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