>假设数组 lst 的索引是一个集合。在下面的程序中，我打印了数组 lst 的 k=1,2,3 的所有可能的唯一子集。如您所见，每个子集元素都有一个计数器。例如元素 23 有子集元素 (3， 5(。我想做的是，通过仅访问计数器，我希望能够构建元素，例如，如果我的计数器值为 23，我应该能够创建 (3,5(。显然，我想这样做而不将所有这些可能的组合存储在内存中。谁能帮我？
lst = [0,1,2,3,4,5,6]
counter=0
for i in range(len(lst)):
print("counter:",counter,"(",i,")", end="t")
counter+=1
print()
for i in range(len(lst)):
for j in range(i+1,len(lst),1):
print("counter:",counter,"(",i,",",j,")", end="t")
counter+=1
print()
for i in range(len(lst)):
for j in range(i+1,len(lst),1):
for k in range(j+1,len(lst),1):
print("counter:",counter,"(",i,",",j,",",k,")", end="t")
counter+=1
print()
结果：
counter: 0 ( 0 ) counter: 1 ( 1 ) counter: 2 ( 2 ) counter: 3 ( 3 ) counter: 4 ( 4 ) counter: 5 ( 5 ) counter: 6 ( 6 )
counter: 7 ( 0 , 1 ) counter: 8 ( 0 , 2 ) counter: 9 ( 0 , 3 ) counter: 10 ( 0 , 4 ) counter: 11 ( 0 , 5 ) counter: 12 ( 0 , 6 )
counter: 13 ( 1 , 2 ) counter: 14 ( 1 , 3 ) counter: 15 ( 1 , 4 ) counter: 16 ( 1 , 5 ) counter: 17 ( 1 , 6 )
counter: 18 ( 2 , 3 ) counter: 19 ( 2 , 4 ) counter: 20 ( 2 , 5 ) counter: 21 ( 2 , 6 )
counter: 22 ( 3 , 4 ) counter: 23 ( 3 , 5 ) counter: 24 ( 3 , 6 )
counter: 25 ( 4 , 5 ) counter: 26 ( 4 , 6 )
counter: 27 ( 5 , 6 )
counter: 28 ( 0 , 1 , 2 ) counter: 29 ( 0 , 1 , 3 ) counter: 30 ( 0 , 1 , 4 ) counter: 31 ( 0 , 1 , 5 ) counter: 32 ( 0 , 1 , 6 ) counter: 33 ( 0 , 2 , 3 ) counter: 34 ( 0 , 2 , 4 ) counter: 35 ( 0 , 2 , 5 ) counter: 36 ( 0 , 2 , 6 ) counter: 37 ( 0 , 3 , 4 ) counter: 38 ( 0 , 3 , 5 ) counter: 39 ( 0 , 3 , 6 ) counter: 40 ( 0 , 4 , 5 ) counter: 41 ( 0 , 4 , 6 ) counter: 42 ( 0 , 5 , 6 )
counter: 43 ( 1 , 2 , 3 ) counter: 44 ( 1 , 2 , 4 ) counter: 45 ( 1 , 2 , 5 ) counter: 46 ( 1 , 2 , 6 ) counter: 47 ( 1 , 3 , 4 ) counter: 48 ( 1 , 3 , 5 ) counter: 49 ( 1 , 3 , 6 ) counter: 50 ( 1 , 4 , 5 ) counter: 51 ( 1 , 4 , 6 ) counter: 52 ( 1 , 5 , 6 )
counter: 53 ( 2 , 3 , 4 ) counter: 54 ( 2 , 3 , 5 ) counter: 55 ( 2 , 3 , 6 ) counter: 56 ( 2 , 4 , 5 ) counter: 57 ( 2 , 4 , 6 ) counter: 58 ( 2 , 5 , 6 )
counter: 59 ( 3 , 4 , 5 ) counter: 60 ( 3 , 4 , 6 ) counter: 61 ( 3 , 5 , 6 )
counter: 62 ( 4 , 5 , 6 )
考虑一下幂集函数的这个定义：
def compress(it, n):
for v in it:
if n & 1:
yield v
n >>= 1
def powerset(s):
return [compress(s, i) for i in range(1 << len(s))]
这将按二进制顺序枚举子集。
我没有完整的答案，只有一些提示来指导你的推理。您可以将索引视为一个扭曲的数值系统，其中没有每个数字位置的所有数字。
让我们n = len(lst)那么 1 索引子集的数量是 n1 = n,2 索引子集的数量是 n2 = n*(n+1)//2 - n1,3 索引子集的数量是 n3 = n*(n+1)*(n+2)//8 - n2 - n1，依此类推......在您的示例中，n1 = 7，n2 = 21 和 n3 = 35，当然还有 n1+n2+n3 = 63
所以我想执行欧几里得分解的一些变体，在n1、n2和n3上使用组合的//和 % 运算符应该提供正确的子集。但这并非完全微不足道...