0

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
  }
]
pygon
  • 3
  • 2
  • As there a minimum number of items to select? Is there a minimum/maximum to select from **each** table? Can items come from one table only? – trincot Apr 25 '22 at 17:34
  • @trincot Excellent questions. My answer assumes no, no, and yes respectively. Changing those up front makes it significantly more complicated. – btilly Apr 25 '22 at 18:36

1 Answers1

1

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)).

btilly
  • 43,296
  • 3
  • 59
  • 88