5
\$\begingroup\$

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.

| improve this question | | | | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the tips. \$\endgroup\$ – Sab Sep 26 '19 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.