python - 大小有序幂集的索引

Question

我希望能够在不将整个集合扩展到内存的情况下索引幂集的元素(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]

Answer 1

我认为您可以分两步完成。第一步是 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

确定尺寸后，您可以使用 combinatorial number system从词典顺序中找到正确的 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 的 k 组合的数量，_nC_k(我称之为 梳子)。 This other question有几个找到该值的建议解决方案，包括 scipy.misc.comb、gmpy.comb 和一些纯 python 实现。或者，因为它被重复调用并连续增加值(例如 comb(n, 0)、comb(n, 1) 等或 comb(k, k)、comb(k+1, k) 等)，您可以改用内联计算，利用先前计算的值来提供更好的性能。

示例用法(在上面链接的问题中使用最低限度改编自 J.F. Sebastian's answer 的 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 从幂集中产生一系列值，由 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))

如果生成器传递的是 slice 对象而不是 int 。这将使您通过简单地将其主体转换为:return self[:] 来使 __iter__ 更快。​​