N色元素的有效组合,颜色数量受到限制

Question

给定一组用C颜色着色的N个元素,如何找到包含不超过最多M种颜色的长度L的每种可能组合？

我尝试使用itertools.combinations生成所有可能组合的算法,然后筛选出那些不具有最大颜色condiction的组合.

from itertools import combinations as cb

def allowed_combinations(elements, combination_size=4, max_colors=3):

    colors = set([c for k, c in elements.items()])
    combinations = cb(elements, combination_size)
    for combination in combinations:
        colors = set([elements[element] for element in combination])
        if len(colors) > max_colors:
            continue
        yield combination


elements = dict()
elements['A'] = 'red'
elements['B'] = 'red'
elements['C'] = 'blue'
elements['D'] = 'blue'
elements['E'] = 'green'
elements['F'] = 'green'
elements['G'] = 'green'
elements['H'] = 'yellow'
elements['I'] = 'white'
elements['J'] = 'white'
elements['K'] = 'black'

combinations = allowed_combinations(elements)

for c in combinations:
    for element in c:
        print("%s-%s" % (element, elements[element]))
    print "\n"

输出如下:

A-red
C-blue
B-red
E-green


A-red
C-blue
B-red
D-blue


A-red
C-blue
B-red
G-green


A-red
C-blue
B-red
F-green

...

问题是产生所有可能的组合在计算上可能非常昂贵.例如,在我的情况下,L通常为6,元素N的数量约为50,因此它给出了Bin(50,6)= 15890700可能的组合.如果组合中允许的最大颜色数量很小,则大多数组合是"无用的",因此它们在过滤步骤中被丢弃.我的直觉是我应该在组合步骤之前/之前进行过滤步骤,以避免组合的展开,但我不知道如何.

Answer 1

组合问题因易于表述但可能难以解决而臭名昭著。对于这个，我itertools根本不会使用，而是编写一个自定义生成器。例如，

def combs(elt2color, combination_size=4, max_colors=3):

    def inner(needed, index):
        if needed == 0:
            yield result
            return
        if n - index < needed:
            # not enough elements remain to reach
            # combination_size
            return
        # first all results that don't contain elts[index]
        for _ in inner(needed, index + 1):
            yield result
        # and then all results that do contain elts[index]
        needed -= 1
        elt = elts[index]
        color = elt2color[elt]
        color_added = color not in colors_seen
        colors_seen.add(color)
        if len(colors_seen) <= max_colors:
            result[needed] = elt
            for _ in inner(needed, index + 1):
                yield result
        if color_added:
            colors_seen.remove(color)

    elts = tuple(elt2color)
    n = len(elts)
    colors_seen = set()
    result = [None] * combination_size
    for _ in inner(combination_size, 0):
        yield tuple(result)

然后：

elt2color = dict([('A', 'red'), ('B', 'red'), ('C', 'blue'),
                  ('D', 'blue'), ('E', 'green'), ('F', 'green'),
                  ('G', 'green'), ('H', 'yellow'), ('I', 'white'),
                  ('J', 'white'), ('K', 'black')])
for c in combs(elt2color):
    for element in c:
        print("%s-%s" % (element, elements[element]))
    print "\n"

生成与后处理代码相同的 188 种组合，但一旦它跨越的max_colors颜色超过颜色，就会在内部放弃部分组合。没有办法改变itertools函数内部的功能，所以当你想控制它时，你需要自己动手。

使用itertools

这是另一种方法，首先生成具有 1 种颜色的所有解决方案，然后生成 2 种颜色的解决方案，依此类推。 itertools可以直接用于大部分工作，但在最低级别仍然需要一个自定义生成器。我发现这比完全自定义的生成器更难理解，但对您来说可能更清楚：

def combs2(elt2color, combination_size=4, max_colors=3):
    from collections import defaultdict
    from itertools import combinations
    color2elts = defaultdict(list)
    for elt, color in elt2color.items():
        color2elts[color].append(elt)

    def at_least_one_from_each(iterables, n):
        if n < len(iterables):
            return # impossible
        if not n or not iterables:
            if not n and not iterables:
                yield ()
            return
        # Must have n - num_from_first >= len(iterables) - 1,
        # so num_from_first <= n - len(iterables) + 1
        for num_from_first in range(1, min(len(iterables[0]) + 1,
                                           n - len(iterables) + 2)):
            for from_first in combinations(iterables[0],
                                           num_from_first):
                for rest in at_least_one_from_each(iterables[1:],
                                             n - num_from_first):
                    yield from_first + rest

    for numcolors in range(1, max_colors + 1):
        for colors in combinations(color2elts, numcolors):
            # Now this gets tricky.  We need to pick
            # combination_size elements across all the colors, but
            # must pick at least one from each color.
            for elements in at_least_one_from_each(
                    [color2elts[color] for color in colors],
                    combination_size):
                yield elements

我没有对这些进行计时，因为我不在乎；-) 完全自定义生成器的单个result列表被重用于构建每个输出，这大大降低了动态内存周转率。from_first第二种方法通过将多个级别的和元组粘贴在一起而产生大量内存搅动rest- 这几乎是不可避免的，因为它用于在每个级别itertools生成from_first元组。

在内部，itertools函数几乎总是以与第一个代码示例更相似的方式工作，并且出于相同的原因，尽可能地重用内部缓冲区。

还有一个

这更多是为了说明一些微妙之处。我考虑了如果我要在 C 中将这个功能作为一个itertools函数来实现，我会做什么。所有itertools函数首先都是在 Python 中原型化的，但是以半低级的方式，简化为使用小整数向量（没有“内循环”使用集合、字典、序列切片或将部分结果序列粘贴在一起）初始化后尽可能O(1)在简单的原生 C 类型上进行最坏情况的时间操作）。

在更高的层次上，itertools这个函数将接受任何可迭代作为其主要参数，并且几乎肯定可以保证按字典索引顺序返回组合。所以这里的代码可以完成所有这些工作。除了iterable参数之外，它还需要一个elt2ec映射，它将每个元素从可迭代对象映射到其等价类（对您来说，这些是命名颜色的字符串，但任何可用作字典键的对象都可以用作等价类）：

def combs3(iterable, elt2ec, k, maxec):
    # Generate all k-combinations from `iterable` spanning no
    # more than `maxec` equivalence classes.
    elts = tuple(iterable)
    n = len(elts)
    ec = [None] * n  # ec[i] is equiv class ordinal of elts[i]
    ec2j = {} # map equiv class to its ordinal
    for i, elt in enumerate(elts):
        thisec = elt2ec[elt]
        j = ec2j.get(thisec)
        if j is None:
            j = len(ec2j)
            ec2j[thisec] = j
        ec[i] = j
    countec = [0] * len(ec2j)
    del ec2j

    def inner(i, j, totalec):
        if i == k:
            yield result
            return
        for j in range(j, jbound[i]):
            thisec = ec[j]
            thiscount = countec[thisec]
            newtotalec = totalec + (thiscount == 0)
            if newtotalec <= maxec:
                countec[thisec] = thiscount + 1
                result[i] = j
                yield from inner(i+1, j+1, newtotalec)
                countec[thisec] = thiscount

    jbound = list(range(n-k+1, n+1))
    result = [None] * k
    for _ in inner(0, 0, 0):
         yield (elts[i] for i in result)

（请注意，这是 Python 3 代码。）正如所宣传的，没有什么inner()比用一个小整数索引向量更奇特的了。使它可以直接转换为 C 的唯一剩下的事情就是删除递归生成。这很乏味，而且因为它不会说明任何特别有趣的事情，所以我将忽略它。

不管怎样，有趣的是时间安排。正如评论中所述，计时结果很大程度上受到您使用的测试用例的影响。 combs3()这里有时是最快的，但并不经常！它几乎总是比我原来的快combs()，但通常比我combs2()或@GarethRees 的可爱慢constrained_combinations()。

combs3()那么，当优化“几乎一直到无意识;-) C级操作”时，怎么会出现这种情况呢？简单的！它仍然是用 Python 编写的。 combs2()并constrained_combinations()使用 C 代码itertools.combinations()来完成大部分工作，这带来了天壤之别。 如果用 C 语言编码的话，combs3()会绕着它们转一圈。

当然，其中任何一个都可以比allowed_combinations()原始帖子中的运行速度无限快 - 但那个也可以是最快的（例如，选择任何输入，其中max_colors如此大以至于不排除任何组合 - 然后allowed_combinations()浪费很少的精力，而所有这些其他人增加了额外的大量额外开销来“优化”从未发生过的修剪）。