我想生成将列表中的索引与“插槽”相关联的组合.例如,(0,1)表示0和1属于同一时隙,而2属于另一个时隙. (0,1,1)表示1,2,3属于同一时隙,而0本身属于同一时隙.在此示例中,0和1只是识别这些插槽的方法,但不包含我的使用信息.
因此,对于我的目的,0)与(1,1)绝对相同,并且(0,1)等同于(1,0).
经典的笛卡尔积产生了许多我想要摆脱的重复.
这是我通过itertools.product获得的：
>>> LEN,SIZE = (3,1)
>>> list(itertools.product(range(SIZE+1),repeat=LEN))
>>>
[(0,0),1),(1,1)]
这就是我想得到的：
>>> [(0,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
最佳答案
我首先提出以下意见：
>每个组合的第一个元素必须为0.
>第二个元素必须是0或1.
>第三个元素必须是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)]
>>> list(assignments(3,2))
[(0,1)]
>>> list(assignments(3,3))
[(0,2)]
"""
if n == 0:
yield ()
return
aa = list(assignments(n - 1,used))
for first in range(used):
for a in aa:
yield (first,) + a
if used < m:
for a in assignments(n - 1,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,number=1)
540.693009853363