索引到大小有序功率集

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

一旦确定了大小,就可以使用组合数系统从词典排序中找到正确的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组合的数量.这另一个问题具有发现价值,包括一些建议的解决方案scipy.misc.comb,gmpy.comb以及一些纯Python实现.或者,因为它与连续增加值重复调用(如comb(n, 0),comb(n, 1)等,或者comb(k, k),comb(k+1, k)等),你也可以使用一个内嵌的计算是利用先前计算的值,以提供更好的性能.

示例用法(使用comb最低限度改编自JF Sebastian在上面链接的问题中的答案的函数):

>>> 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[:].