5

我正在寻找一种有效的方法来从大小为 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 个子集是可重复的，并且如果它们不需要的话，它们不会意外地接近每个子集。

4

2 回答 2

7

好吧，我仍然很喜欢这个 ;-)

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

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)
于 2013-09-12T02:12:23.067 回答
4

我认为这是一个难题。这是一个实用的方法：跟踪每个元素full_set被返回的次数，并努力使用“最不流行”（到目前为止）元素生成下一个子集。例如，下面的代码产生：

>>> for s in gen_subsets_special(set(range(5)), 1, 20):
>>>    print s
set([0])
set([1])
set([2])
set([3])
set([4])

所以它只产生 5 种可能性中的每一种，而不是产生 20 个，而是退出（它知道没有其他可能性）。如果 K > N-choose-M，则可以轻松更改代码以引发异常。

一个更有趣的例子：

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

所以至少它会生成不重叠的子集，直到这变得不可能;-)

这是代码。它是纯 Python (2.7.5)，不使用 numpy 功能。不将 K 作为参数传递会更习惯- 生成器产生的项目数通常由调用者控制（当调用者完成时，它只是停止恢复生成器）。

def gen_subsets_special(full_set, M, K):
    # generate K M-subsets of full_set, "far apart".
    from itertools import combinations
    elements = list(full_set)
    # index2count[i] = # of returned subsets containing
    # elements[i]
    index2count = dict((i, 0) for i in range(len(elements)))
    seen = set()
    for _ in xrange(K):
        bycount = sorted(index2count, key=index2count.get)
        # the least popular indices are at the start;
        # combinations generates results in lexicographic
        # index order, so will return combinations containing
        # the least popular indices first
        for raw in combinations(bycount, M):
            raw = tuple(sorted(raw)) # normalize
            if raw not in seen:
                break
        else:
            # all M-combinations have already been seen
            return
        seen.add(raw)
        for i in raw:
            index2count[i] += 1
        yield set(elements[i] for i in raw)

请注意，生成的序列是否可重复主要取决于list(full_set)每次运行时返回相同的列表。但是没有明确的集合元素出现的顺序。如果集合元素支持比较，则可以通过使用获得可重复性

    elements = sorted(full_set)

反而。

稍后：请注意，所有不同的返回子集对的交集的大小之和可以很容易地从index2count向量中计算出来：它是

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

清除？如果给定元素恰好出现在n子集中，则有 n-choose-2 (= n*(n-1)/2) 对子集，该元素在它们的交集中，因此该元素贡献了 n-choose -2 到总计数。这是为什么努力平衡计数在这里很有帮助的一个更正式的原因。

于 2013-09-11T04:16:39.063 回答