按照sku相关性将Order分组，并查集思路解法

OrderSplitDemo.py

class Order(object):
  def __init__(self, order_id, sku_id_s):
    self.order_id = order_id
    self.sku_id_s = sku_id_s
  def __repr__(self):
    return repr(self.order_id)

class OrderGroup(object):
  def __init__(self):
    self.head_group = self
    self.order_s = []  # list<Order>
  def __repr__(self):
    return '<#{}, #{}, {}>'.format(hex(id(self)), hex(id(self.head_group)), repr(self.order_s))

def split_orders_to_disjoint_order_list(order_s):   # list<Order> => list<list<Order>
  sku_id_to_group = {}   # skuid => OrderGroup
  for order in order_s:
    # init order group
    hitted_groups = []
    for sku_id in order.sku_id_s:
      group = sku_id_to_group.get(sku_id)
      if group is None:
        group = OrderGroup()
        sku_id_to_group[sku_id] = group
      hitted_groups.append(group)
    print '\t', order, hitted_groups
    # merge group if needed, move all orders to head group
    if len(hitted_groups) > 1:
      head_group = hitted_groups[0].head_group
      for group in hitted_groups[1:]:
        old_head_group = group.head_group
        group.head_group = head_group
        head_group.order_s.extend(old_head_group.order_s)
        old_head_group.order_s = []
    # add current order to head group
    if len(hitted_groups) > 0:
      hitted_groups[0].head_group.order_s.append(order)
  result = []
  for group in sku_id_to_group.values():
    if group.head_group == group and len(group.order_s) > 0:
      result.append(group.order_s)
  return result

print split_orders_to_disjoint_order_list([
  Order(1000, [1]),
  Order(1001, [2,9]),
  Order(1003, [3]),
  Order(1004, [4,8,9]),
  Order(1005, [5]),
  Order(1007, [3,4]),
  Order(1008, [1,4]),
  ])