Guest User

Code for SO: https://ru.stackoverflow.com/questions/863851

a guest
Aug 6th, 2018
30
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. BOX_SIZE = 3     # максимальный "размер" коробки
  2. OBJS_COUNT = 12  # количество элементов во входном списке
  3. SIZE_B = 2       # "размер" "большого" элемента
  4.  
  5.  
  6. class Box(object):
  7.  
  8.     def __init__(self, index, size):
  9.         super().__init__()
  10.  
  11.         self._items = []
  12.         self._size = size
  13.  
  14.         self.index = index
  15.  
  16.     def __repr__(self):
  17.         return 'Box%(index)s(%(items)s)' % {
  18.             'index': self.index,
  19.             'items': str([item for item in self._items])
  20.         }
  21.  
  22.     @property
  23.     def size(self):
  24.         if not self._items:
  25.             return 0
  26.         return sum(item.size for item in self._items)
  27.  
  28.     def add(self, item):
  29.         from itertools import permutations
  30.  
  31.         if self.size + item.size <= self._size:
  32.             self._items.append(item)
  33.             return
  34.  
  35.         items = self._items.copy()
  36.         items.append(item)
  37.         for comb in permutations(items, len(self._items)):
  38.  
  39.             if not sum(item.size for item in comb) == self._size:
  40.                 continue
  41.  
  42.             diff = set(self._items).difference(set(comb))
  43.  
  44.             self._items = list(comb)
  45.  
  46.             try:
  47.                 return diff.pop()
  48.             except KeyError:
  49.                 return
  50.  
  51.         return item
  52.  
  53.     def complete(self, strict=True):
  54.         if strict:
  55.             return self.size == self._size
  56.         return self.size >= self._size
  57.  
  58.  
  59. class BoxItem(object):
  60.  
  61.     def __init__(self, name):
  62.         super().__init__()
  63.  
  64.         self.name = name
  65.  
  66.     def __repr__(self):
  67.         return str(self.name)
  68.  
  69.     @property
  70.     def size(self):
  71.         if self.name.startswith('B'):
  72.             return SIZE_B
  73.         return 1
  74.  
  75.  
  76. import random
  77. objs = []
  78. index_B = 0
  79. index_s = 0
  80. prefixes = random.choices('Bs', k=OBJS_COUNT)
  81. for prefix in prefixes:
  82.     index = 0
  83.     if prefix == 'B':
  84.         index_B += 1
  85.         index = index_B
  86.     else:
  87.         index_s += 1
  88.         index = index_s
  89.     name = prefix + str(index)
  90.  
  91.     objs.append(BoxItem(name))
  92.  
  93. print('objs', objs)
  94.  
  95. border = OBJS_COUNT * SIZE_B / BOX_SIZE
  96.  
  97. box = None
  98. iteration = 0
  99. result = []
  100. while iteration < border:
  101.  
  102.     if box is None:
  103.         box = Box(iteration, BOX_SIZE)
  104.         box.add(objs.pop(0))
  105.  
  106.     empty = set()
  107.     for index, item in enumerate(objs):
  108.  
  109.         obj = box.add(item)
  110.         objs[index] = obj
  111.  
  112.         if obj is None:
  113.             empty.add(index)
  114.  
  115.         if box.complete():
  116.             break
  117.  
  118.     for index, pos in enumerate(empty):
  119.         del objs[pos - index]
  120.  
  121.     if box.complete() or not objs:
  122.         result.append(box)
  123.         box = None
  124.  
  125.     if not objs:
  126.         break
  127.  
  128.     iteration += 1
  129.  
  130. print('-' * 64)
  131. print('iterations:')
  132. print('-' * 8)
  133. print('border:', border)
  134. print('total:', iteration)
  135.  
  136. print('-' * 64)
  137. print('orphans', objs)
  138. if objs:
  139.     box = box or Box(len(result), BOX_SIZE)
  140.     for orphan in objs:
  141.         box._items.append(orphan)
  142.     result.append(box)
  143.  
  144. print('-' * 64)
  145. print('result', result)
RAW Paste Data