如何按组内篮子共有物品≥6的规则对篮子对象做无重复分组

该需求属于带硬约束的无重叠聚类场景，要求组内任意两个篮子共享物品数量≥6，且每个篮子仅归属一个分组。此前组合方法产生冗余的核心原因是未做篮子归属状态标记，导致同一篮子被划入多个候选分组。

实现步骤 #

• 预处理：先对食品列表去重，将每个篮子的物品转换为集合以加速交集计算，同时建立「食品-包含该食品的篮子」倒排索引用于快速筛选候选篮子，降低遍历复杂度
• 贪心聚类：遍历所有未分配的篮子作为分组种子，按规则构建分组：
  1. 通过倒排索引快速筛选出和种子篮子共享至少6个物品的候选篮子，避免全量遍历
  2. 候选篮子需满足：和当前组内所有已存在的篮子的交集长度≥6，且未被分配
  3. 分组构建完成后，标记组内所有篮子为已分配，归入结果集

可运行代码 #

from typing import Generic, TypeVar, List, Dict, Set
import random
from uuid import uuid4
import attr
from collections import defaultdict

T = TypeVar("T")

# 先对食品列表去重，避免采样出重复物品
food = ['apple', 'banana','grapes','orange','potato','kiwi','pomegranate','blueberry','strawberry','cantalope','honeydew','papaya','mango','raspberry',
        'celery','carrot','potato','raddish','lettuce','tomato','garlic','onion','cabbage','corn','shallot','peas','squash','broccoli','spinach']
food = list(set(food))

@attr.dataclass
class Basket(Generic[T]):
    items: List[T]
    volume: int
    id: str = attr.ib(factory=lambda: str(uuid4()))
    # 新增物品集合属性，避免重复转集合
    item_set: Set[T] = attr.ib(init=False)
    # 分配标记
    is_assigned: bool = attr.ib(default=False)

    def __attrs_post_init__(self):
        self.item_set = set(self.items)


# 生成篮子
basket_names = [f"basket{i}" for i in range(1, 10001)]
baskets: List[Basket[str]] = [
    Basket(items=random.sample(food, 10), volume=random.randint(0, 1000), id=name)
    for name in basket_names
]

# 建立倒排索引：食品 -> 包含该食品的篮子列表
food_to_baskets: Dict[str, List[Basket]] = defaultdict(list)
for basket in baskets:
    for item in basket.item_set:
        food_to_baskets[item].append(basket)

# 分组结果存储
groups: List[List[Basket]] = []

for basket in baskets:
    if basket.is_assigned:
        continue
    # 新建分组，以当前篮子为种子
    current_group = [basket]
    basket.is_assigned = True

    # 快速筛选候选篮子：和种子篮子共享至少6个物品的篮子
    candidate_count: Dict[Basket, int] = defaultdict(int)
    for item in basket.item_set:
        for candidate in food_to_baskets[item]:
            if not candidate.is_assigned:
                candidate_count[candidate] += 1
    # 只保留共享物品≥6的候选
    candidates = [c for c, cnt in candidate_count.items() if cnt >=6]

    # 逐个校验候选是否符合组内约束
    for candidate in candidates:
        if candidate.is_assigned:
            continue
        # 和组内所有篮子的交集都≥6才能加入
        valid = True
        for member in current_group:
            if len(candidate.item_set & member.item_set) <6:
                valid = False
                break
        if valid:
            current_group.append(candidate)
            candidate.is_assigned = True

    groups.append(current_group)

# 结果验证
print(f"总分组数：{len(groups)}")
print(f"包含2个及以上篮子的分组数：{len([g for g in groups if len(g)>=2])}")
print(f"未匹配到其他篮子、单独成组的数量：{len([g for g in groups if len(g)==1])}")

可选优化 #

如果需要进一步提升运行速度，可以在候选校验阶段提前终止不符合条件的判断，也可以基于物品特征做哈希分桶，减少候选集规模。如果要求所有分组必须包含至少2个篮子，可以把单独成组的篮子统一归入未分配集合单独处理。

内容的提问来源于stack exchange，提问作者Ethan Carter