python - 无论顺序如何，都生成重复列表

Question

我想生成将列表中的索引与“插槽”相关联的组合。例如，(0, 0, 1) 表示 0 和 1 属于同一个插槽，而 2 属于另一个。 (0, 1, 1, 1) 表示 1, 2, 3 属于同一个槽，而 0 是单独的。在此示例中，0 和 1 只是标识这些插槽的方式，但不携带我使用的信息。

因此，就我而言，(0, 0, 0) 与 (1, 1, 1) 完全相同，而 (0, 0, 1) 等价于(1, 1, 0)。

经典的笛卡尔积产生了很多我想摆脱的重复。

这是我通过 itertools.product 获得的:

>>> LEN, SIZE = (3,1)
>>> list(itertools.product(range(SIZE+1), repeat=LEN))
>>>
[(0, 0, 0),
(0, 0, 1),
(0, 1, 0),
(0, 1, 1),
(1, 0, 0),
(1, 0, 1),
(1, 1, 0),
(1, 1, 1)]

这就是我想要得到的:

>>> [(0, 0, 0),
(0, 0, 1),
(0, 1, 0),
(0, 1, 1)]

小列表很容易，但我不太明白如何处理大列表。你有什么建议吗？

如果不清楚，请告诉我，以便我澄清我的问题。谢谢!

编辑:根据 Sneftel 的回答，这个函数似乎有效，但我不知道它是否真的产生了所有结果:

def test():
    for p in product(range(2), repeat=3):
        j=-1
        good = True
        for k in p:
            if k> j and (k-j) > 1:
                good = False
            elif k >j:
                j = k
        if good:
            yield p

Answer 1

我将从以下几点开始:

1. 每个组合的第一个元素必须为0。
2. 第二个元素必须是0或1。
3. 第三个元素必须为0、1或2，但只有第二个元素为1时才能为2。

这些观察表明了以下算法:

def assignments(n, m, used=0):
    """Generate assignments of `n` items to `m` indistinguishable
    buckets, where `used` buckets have been used so far.

        >>> list(assignments(3, 1))
        [(0, 0, 0)]
        >>> list(assignments(3, 2))
        [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1)]
        >>> list(assignments(3, 3))
        [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (0, 1, 2)]

    """
    if n == 0:
        yield ()
        return
    aa = list(assignments(n - 1, m, used))
    for first in range(used):
        for a in aa:
            yield (first,) + a
    if used < m:
        for a in assignments(n - 1, m, used + 1):
            yield (used,) + a

这会在几秒钟内处理您的用例(12 个项目，5 个桶):

>>> from timeit import timeit
>>> timeit(lambda:list(assignments(12, 5)), number=1)
4.513746023178101
>>> sum(1 for _ in assignments(12, 5))
2079475

如果将其修改为处理 (12, 5)用例:

>>> timeit(lambda:list(test(12, 5)), number=1)
540.693009853363