How to take 2 Tables of data, and come up with combination that fit the restrictions-CodePudding

So, what I would like to do is use these two tables here, and come up with a combination of items from Table 1 that will add up to the total from the combination of Table 2 1500 or less, but can never go under the value of Table 2 500. Then at the end it should return the combination which will be later used in the rest of the code.

For example lets say we came up with a combination and this combination uses all 4 items in Table 2, we are able to use all of them since it meets the restrictions, and now if we add all the values in Table 2 you get 11,620. Now we have to come up with a combination from Table 1 that has the value that is at least 12,120 but less than 13,120.

If you require more detail about what I'm trying to archive here please let me know!

Restrictions

Each combination can only have up to 4 items
The value of Each item is defined by the "value.

Table 2

[
   {
      "UAID":143071570,
      "assetId":19027209,
      "name":"Perfectly Legitimate Business Hat",
      "value":10549
   },
   {
      "UAID":143334875,
      "assetId":19027209,
      "name":"Perfectly Legitimate Business Hat",
      "value":10549
   },
   {
      "UAID":1235149469,
      "assetId":100425864,
      "name":"Deluxe Game Headset",
      "value":1795
   },
   {
      "UAID":2756318596,
      "assetId":20573078,
      "name":"Shaggy",
      "value":1565
   },
   {
      "UAID":3499638196,
      "assetId":20573078,
      "name":"Shaggy",
      "value":1565
   },
   {
      "UAID":11002211144,
      "assetId":102618797,
      "name":"DJ Remix's Goldphones",
      "value":7393
   },
   {
      "UAID":50913661583,
      "assetId":4390875496,
      "name":"Diamond Crystal Circlet",
      "value":4886
   }
]

Table 2

[
  {
     "UAID":672099668,
     "assetId":60888284,
     "name":"DarkAge Ninjas: Dual Kamas",
     "value":4461
  },
  {
     "UAID":6599510068,
     "assetId":554663566,
     "name":"Manicbot 10000",
     "value":4319
  },
  {
     "UAID":63414825508,
     "assetId":91679217,
     "name":"Sailing Hat",
     "value":1886
  },
  {
     "UAID":150428091864,
     "assetId":8785277745,
     "name":"Cincinnati Bengals Super Bowl LVI Helmet",
     "value":954
  }
]

CodePudding user response：

This is a technique that I've shown multiple times, and nobody else seems to have heard of.

The idea is the same as Finding all possible combinations of numbers to reach a given sum but more complicated since we need to do it repeatedly. It is to create a data structure from which subsets can be easily found that sum to a particular value.

class SubsetSumIter:
    def __init__ (self, data):
        self.data = data

        # Build up an auxilliary data structure to find solutions.
        last_index = {0: [-1]}
        for i in range(len(data)):
            for s in list(last_index.keys()):
                new_s = s   data[i]['value']
                if new_s in last_index:
                    last_index[new_s].append(i)
                else:
                    last_index[new_s] = [i]

        self.last_index_by_target = last_index
        self.targets = sorted(last_index.keys())

    def subsets_at_target(self, target, max_i=None):
        if max_i is None:
            max_i = len(self.data)

        for i in self.last_index_by_target[target]:
            if i == -1:
                yield [] # empty sum
            elif max_i <= i:
                break # went past our solutions
            else:                                                                                                              
                for answer in self.subsets_at_target(target - self.data[i]["value"], i):
                    answer.append(self.data[i])
                    yield answer

    def subsets_in_range(self, lower, upper):
        i_min = 0
        i_max = len(self.targets)
        while 1 < i_max - i_min:
            i_mid = (i_min   i_max) // 2
            if self.targets[i_mid] < lower:
                i_min = i_mid
            else:
                i_max = i_mid

        i = i_min   1
        while i < len(self.targets) and self.targets[i] <= upper:
            for answer in self.subsets_at_target(self.targets[i]):
                yield answer
            i = i 1

From this we can create your desired join condition as follows:

def complex_join(table1, table2):
    iter1 = SubsetSumIter(table1)
    iter2 = SubsetSumIter(table2)

    # For each sum from table2
    for target in iter2.targets:
        # For each combination from table 1 in our desired range
        for subset1 in iter1.subsets_in_range(target   500, target   1500):
            # For each combination from table 2 that gets that target
            for subset2 in iter2.subsets_at_target(target):
                yield (subset1, subset2)

And to find all 38 solutions to your example:

t1 = [
   {
      "UAID":143071570,
      "assetId":19027209,
      "name":"Perfectly Legitimate Business Hat",
      "value":10549
   },
   {
      "UAID":143334875,
      "assetId":19027209,
      "name":"Perfectly Legitimate Business Hat",
      "value":10549
   },
   {
      "UAID":1235149469,
      "assetId":100425864,
      "name":"Deluxe Game Headset",
      "value":1795
   },
   {
      "UAID":2756318596,
      "assetId":20573078,
      "name":"Shaggy",
      "value":1565
   },
   {
      "UAID":3499638196,
      "assetId":20573078,
      "name":"Shaggy",
      "value":1565
   },
   {
      "UAID":11002211144,
      "assetId":102618797,
      "name":"DJ Remix's Goldphones",
      "value":7393
   },
   {
      "UAID":50913661583,
      "assetId":4390875496,
      "name":"Diamond Crystal Circlet",
      "value":4886
   }
]

t2 = [
  {
     "UAID":672099668,
     "assetId":60888284,
     "name":"DarkAge Ninjas: Dual Kamas",
     "value":4461
  },
  {
     "UAID":6599510068,
     "assetId":554663566,
     "name":"Manicbot 10000",
     "value":4319
  },
  {
     "UAID":63414825508,
     "assetId":91679217,
     "name":"Sailing Hat",
     "value":1886
  },
  {
     "UAID":150428091864,
     "assetId":8785277745,
     "name":"Cincinnati Bengals Super Bowl LVI Helmet",
     "value":954
  }
]


for answer in complex_join(t1, t2):
    print(answer)

And if you want to get a (possibly large) list at the end you can simply list(complex_join(t1, t2)).