无论顺序如何,都生成重复列表

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) 用例，这比您在答案末尾给出的函数（调用product然后删除无效分配的函数）要快得多：

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