python - 确定性python生成器，用于集合的K个不同的M大小的子集

我正在寻找一种有效的方法来从大小为N的集合S生成许多M个大小的子集。

理想情况下，我想生成所有这些，但是因为我将它们用于其他计算，所以这变得不可行。

相反，我想生成S的K个不同的子集，以使K个选择的子集最小化K个子集之间所有成对相交的大小之和。

换句话说，如果我有K个子集
我将所有这些子集进行成对相交。
然后，我将所有这些集合的大小加在一起。
我得到的数字越少越好。

基本上，我希望这些子集彼此尽可能“远离”。
我一直在试图思考如何做到这一点，但是我正在画一个空白。

为了模拟它，同时我编写了这个函数

        def subset_split(full_set, M, K):
            np.random.seed(0) # repeatibility
            seen = set([])
            subset_list = []
            for kx in xrange(K):
                np.random.shuffle(full_set)
                failsafe = 0
                while True:
                    np.random.shuffle(full_set)
                    subset = tuple(full_set[0:M])
                    if not subset in seen:
                        seen.add(subset)
                        subset_list.append(subset)
                        break
                    failsafe += 1
                    if failsafe > 100:
                        break
            return subset_list

它只是生成K个以前从未见过的随机子集。但这并不是我想要的，因为我希望那些K个子集是可重复的，并且在不需要它们时不要意外地接近每个子集。

最佳答案

好吧，我是仍然很开心；-)

停止的地方很明显，我们正在尝试最小化:

sum(n*(n-1)//2 for n in index2count.values())

如果所有值都相同(如果可能)，或者有两个不同的值(例如len(full_set) = 10，则为七个3和三个4)，则这是最小的。这足以编写一个根本不需要计算index2count的生成器。相反，hi是具有两个值中较大者的索引集，lo是其余索引(如果所有(概念性!未计算的)值都相同，lo为空)。

这删除了K参数，并采取了另一种方法来处理重复项:它将忽略它们。在这里跟踪重复项既昂贵又笨拙，重复项实际上应该是预期的，在“随机的”生成器中。如果那使您感到困扰，请将其包装在另一个例程中以清除重复项。

样本输出:

>>> from itertools import islice
>>> for s in islice(gen_subsets_special(set(range(5)), 1), 10):
...    print s
set([4])
set([3])
set([0])
set([1])
set([2])
set([0])
set([3])
set([1])
set([2])
set([4])

>>> for s in islice(gen_subsets_special(set(range(10, 20)), 3), 10):
...    print s
set([17, 18, 10])
set([11, 12, 14])
set([16, 19, 13])
set([12, 13, 15])
set([17, 10, 11])
set([16, 19, 15])
set([17, 18, 14])
set([16, 18, 13])
set([19, 12, 15])
set([10, 11, 14])

这是代码:

def gen_subsets_special(full_set, M, seed=123456):
    # generate randomish M-subsets of full_set, "far apart".
    import random
    from random import sample
    random.seed(seed)
    elements = list(full_set)
    N = len(elements)
    hi = set(range(N))
    lo = set()
    while True:
        assert not (hi & lo)
        assert len(lo | hi) == N
        # First take indices from hi, then (if needed) from lo.
        if len(hi) > M:
            # We can take all of them from hi, with some left over.
            ixhi = set(sample(hi, M))
            ixlo = set()
            # The ixhi counts go down by 1, so move 'em to lo
            hi -= ixhi
            lo |= ixhi
            assert hi
        else:
            # We need to take everything in hi.
            ixhi = hi.copy()
            ixlo = set(sample(lo, M - len(ixhi)))
            hi |= lo - ixlo
            lo = ixlo
        assert not (ixlo & ixhi)
        ix = ixlo | ixhi
        assert len(ix) == M
        yield set(elements[i] for i in ix)

通过构造，所生成序列的每个前缀都会使前缀中所有集合对的交点的总和最小化。大概在我看来；-)

最后，显然是所有索引反复循环的一种变体。这可能是我实际使用的一个:

def gen_subsets_special(full_set, M, seed=123456):
    # generate randomish M-subsets of full_set, "far apart".
    import random
    from random import sample
    random.seed(seed)
    elements = list(full_set)
    allix = set(range(len(elements)))
    takefrom = allix.copy()

    def destructive_sample(n):
        # Remove a random n-subset from takefrom, & return it.
        s = set(sample(takefrom, n))
        takefrom.difference_update(s)
        return s

    while True:
        if len(takefrom) >= M:
            # Get everything from takefrom.
            ix = destructive_sample(M)
        else:
            # We need to take all of takefrom, and more.
            ix = takefrom
            takefrom = allix - ix
            ix |= destructive_sample(M - len(ix))
        assert len(ix) == M
        yield set(elements[i] for i in ix)

关于python - 确定性python生成器，用于集合的K个不同的M大小的子集，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18731919/