10

我希望能够在不将整个集合扩展到内存的情况下索引幂集的元素（a la itertools）

此外，我希望索引是基数排序的。所以索引 0 应该是空集，索引 2**n - 1 应该是所有元素

到目前为止，我发现的大多数文献都涉及以感应方式生成电源组。它不会让您直接进入任何索引。我对这个索引的动机是为分布式执行分割一个问题，如果远程机器可以直接潜入任何地方而不在集群中共享迭代器引用，这将很有帮助。

编辑：Blckknght 建议了我所追求的解决方案，如下所示

from scipy.misc import comb

def kcombination_to_index(combination):
    index = 0
    combination = sorted(combination)
    for k, ck in enumerate(combination):
        index += comb(ck, k+1, exact=True)
    return index

def index_to_kcombination(index, k):
    result = []
    for k in reversed(range(1, k+1)):
        n = 0
        while comb(n, k, exact=True) <= index:
            n +=1
        result.append(n-1)
        index -= comb(n-1, k, exact=True)

    return result

class PowerSet:
    def __init__(self, elements):
        self.elements = elements

    def __len__(self):
        return 2 ** len(self.elements)

    def __iter__(self):
        for i in range(len(self)):
            yield self[i]

    def __getitem__(self, k):
        if not isinstance(k, int):
            raise TypeError
        #k=0 is empty set,
        #k= 1 - 1+n returns subsets of size 1
        for subset_size in range(len(self.elements) + 1):
            number_subsets = comb(len(self.elements), subset_size, exact=True)

            if k >= number_subsets:
                k -= number_subsets
            else:
                break

        #we now want the kth element of a possible permutation of subset_size elements
        indeces = index_to_kcombination(k, subset_size)

        return map(lambda i: self.elements[i], indeces)

if __name__ == "__main__":
    print "index of combination [8, 6, 3, 1, 0] is", kcombination_to_index([8, 6, 3, 1, 0])
    print "5 combination at position 72 is", index_to_kcombination(72,5)

    ps = PowerSet(["a", "b", "c", "d"])

    for subset_idx in range(len(ps)):
        print ps[subset_idx]
4

1 回答 1

8

我认为您可以通过两步过程来做到这一点。第一步就像 Mihai Maruseac 在他的（现已删除）答案中描述的那样，通过迭代可能的大小来找到集合的大小，直到找到合适的大小。这是代码：

def find_size(n, i):
    """Return a tuple, (k, i), where s is the size of the i-1'th set in the
       cardinally-ordered powerset of {0..n-1}, and i is the remaining index
       within the combinations of that size."""
    if not 0 <= i < 2**n:
        raise ValueError('index is too large or small')
    for k in range(n+1):
        c = comb(n, k)
        if c > i:
            return k, i
        else:
            i -= c

一旦确定了大小，就可以使用组合数系统从字典顺序中找到正确的 k 组合：

def pick_set(n, i):
    """Return the i-1'th set in the cardinally-ordered powerset of {0..n-1}"""
    s, i = find_size(n, i)
    result = []
    for k in range(s, 0, -1):
        prev_c = 0
        for v in range(k, n+1):
            c = comb(v, k)
            if i < c:
                result.append(v-1)
                i -= prev_c
                break
            prev_c = c
    return tuple(result)

这两个函数都需要一个函数来计算一组大小为 n、n C k（我称之为comb）的 k 组合的数量。This other question有几个建议的解决方案来查找该值，包括scipy.misc.comb，gmpy.comb以及一些纯python实现。或者，由于它是使用顺序增加的值（例如comb(n, 0),comb(n, 1)等或comb(k, k),comb(k+1, k)等）重复调用的，因此您可以改为使用内联计算，该计算利用先前计算的值来提供更好的性能。

示例用法（使用从JF Sebastian 在上面链接的问题中的回答comb中最小化的函数）：

>>> for i in range(2**4):
        print(i, pick_set(4, i))

0 ()
1 (0,)
2 (1,)
3 (2,)
4 (3,)
5 (1, 0)
6 (2, 0)
7 (2, 1)
8 (3, 0)
9 (3, 1)
10 (3, 2)
11 (2, 1, 0)
12 (3, 1, 0)
13 (3, 2, 0)
14 (3, 2, 1)
15 (3, 2, 1, 0)

请注意，如果您计划迭代组合（就像我在示例中所做的那样），您可能会比运行完整算法更有效，因为有更有效的算法可以找到给定大小的下一个组合（尽管您当您用尽初始大小时，将需要一些额外的逻辑来提升到下一个更大的组合大小）。

编辑：以下是我上面简要提到的一些优化的实现：

首先，有效计算范围n或k值的组合值的生成器：

def comb_n_range(start_n, stop_n, k):
    c = comb(start_n, k)
    yield start_n, c
    for n in range(start_n+1, stop_n):
        c = c * n // (n - k)
        yield n, c

def comb_k_range(n, start_k, end_k):
    c = comb(n, start_k)
    yield start_k, c
    for k in range(start_k+1, end_k):
        c = c * (n - k + 1) // k
        yield k, c

上面代码中的for ... in range(...): c = comb(...); ...位可以调整来使用这些，应该会快一点。

接下来，一个按字典顺序返回下一个组合的函数：

def next_combination(n, c):
    if c[-1] == n-len(c)+1:
        raise ValueError("no more combinations")
    for i in range(len(c)-1, -1, -1):
        if i == 0 or c[i] < c[i-1] - 1:
            return c[:i] + (c[i] + 1,) + tuple(range(len(c)-2-i,-1,-1))

还有一个生成器，用于next_combination从由对象定义的 powerset 中产生一系列值slice：

def powerset_slice(n, s):
    start, stop, step = s.indices(2**n)
    if step < 1:
        raise ValueError("invalid step size (must be positive)")

    if start == 0:
        c = ()
    else:
        c = pick_set(n, start)

    for _ in range(start, stop, step):
        yield c
        for _ in range(step):
            try:
                c = next_combination(n, c)
            except ValueError:
                if len(c) == n:
                    return
                c = tuple(range(len(c), -1, -1))

如果__getitem__传递一个slice对象而不是一个int. 这可以让你__iter__通过简单地将它的身体变成：return self[:].

于 2013-09-23T21:35:23.000 回答