python - 使用 Python 将非唯一实体划分为唯一集合

Question

我有一个项目列表，例如[1,1,1,1,2,2]，我试图找到所有唯一的组，其中这些项目被捆绑到长度为一或两个的元组中。例如，对于上面的组，我想找到以下 10 个可能的分组:

[[(1,),(1,),(1,),(1,),(2,),(2,)],
 [(1,1),(1,),(1,),(2,),(2,)],
 [(1,2),(1,),(1,),(1,),(2,)],
 [(2,2),(1,),(1,),(1,),(1,)],
 [(1,1),(1,1),(2,),(2,)],
 [(1,1),(1,2),(1,),(2,)],
 [(1,2),(1,2),(1,),(1,)],
 [(2,2),(1,1),(1,),(1,)],
 [(1,1),(1,1),(2,2)],
 [(1,1),(1,2),(1,2)]]

我一直在玩 itertools，但只能设法用它来找到唯一可能的元组(例如 set(list(itertools.combinations((1,1,1,1,2,2), 2)))) 和我做的任何搜索都会弹出解决方案，其中每个组的大小是恒定的和/或不考虑元素的重复(example1，example2)。

最终，我正在寻找一种解决方案，适用于所有情况([1,1,1,...,1])，所有情况([ 2,2,2,...,2]) 或包含任意数量的 1 和 2 的一些中间组合。

Answer 1

正如我在评论中指出的那样，输入列表的最大长度至关重要。下面是示例代码，它通过对完整的分区集进行后处理(清除重复项，并清除带有“太大”的片段的分区)来足够快地解决您给出的特定示例。但是对于“长”的原始列表，这将是可怕的低效的:

def part(xs):  # generate all partitions of xs
    xs = tuple(xs)
    n = len(xs)
    def extend(i):
        if i == n:
            yield ()
            return
        this = xs[i]
        for o in extend(i+1):
            yield ((this,),) + o
            for j, p in enumerate(o):
                yield o[:j] + ((this,) + p,) + o[j+1:]
    for o in extend(0):
        yield o

def upart(xs):  # weed out dups, and partitions with a piece bigger than 2
    from collections import Counter
    seen = []
    for p in part(xs):
        if all(len(chunk) <= 2 for chunk in p):
            c = Counter(p)
            if c not in seen:
                seen.append(c)
                yield p

xs = [1,1,1,1,2,2]
for o in upart(xs):
    print o

这会显示您要查找的 10 个唯一分区。

顺便说一句，对于 xs = [1,1,1,1,1,1]，它会产生:

((1,), (1,), (1,), (1,), (1,), (1,))
((1, 1), (1,), (1,), (1,), (1,))
((1, 1), (1, 1), (1,), (1,))
((1, 1), (1, 1), (1, 1))

自定义生成器

正如评论中还指出的那样，如果对一般构建 block 的结果进行后处理效率太低，则需要从头开始“自己动手”。这是一种非常节省空间的方法，通过构建(而不是通过后处理)构建独特的结果。确实没有做到这一点的“通用方法”——它需要分析手头的具体问题，并编写代码来利用你能找到的任何怪癖:

def custom_gen(xs):
    from collections import Counter
    assert all(1 <= i <= 2 for i in xs)
    # There are only 5 unique pieces that can be used:
    pieces = [(1,), (2,), (1, 1), (2, 2), (1, 2)]
    countpieces = {piece: Counter(piece) for piece in pieces}

    def extend(i, n1, n2, result):
        # try all ways of extending with pieces[i];
        # there are n1 1's and n2 2's remaining to be used
        assert n1 >= 0 and n2 >= 0
        if n1 == n2 == 0:
            yield result
            return
        if i == len(pieces):  # dead end
            return
        piece = pieces[i]
        c = countpieces[piece]
        p1 = c[1]
        p2 = c[2]
        # What's the most number of this piece we could
        # possibly take?
        assert p1 or p2
        if p1:
            if p2:
                most = min(n1 // p1, n2 // p2)
            else:
                most = n1 // p1
        else:
            most = n2 // p2
        for count in range(most + 1):
            for t in extend(i+1,
                            n1 - count * p1,
                            n2 - count * p2,
                            result + [piece] * count):
                yield t

    c = Counter(xs)
    for t in extend(0, c[1], c[2], []):
        yield t

请注意，递归永远不会超过 5 层(无论输入列表有多长)，所以我敢打赌，这是最有效的方法，无需对问题的数学进行更深入的分析。