algorithm - 与多个不同大小的容器组合

Question

如果你知道这种问题叫什么，请告诉我(除非你真的知道问题的答案)。

如果我有一组 Z 个对象，是否有一种算法可以将它们放在一堆容器(每个容器都包含一定数量的对象)之间？

为了让问题稍微复杂化，让我们假设我们开始的对象集有一个子集 X。有 X 个容器，每个容器必须包含 X 的一个元素，以及其他对象(如果它有空间) .

目前我能想到的最好的方法是查看 Z 和 X 的析取，我们称它为 Y。然后我们可以生成 z 选择 x 的组合，然后将其扩展为 x 的所有可能组合。

示例:实际问题基本上是在空间中生成所有事件。假设我们有两个事件触发器 (X) 和 2 个事件参数 (Y)，其中 Z = X U Y。每个事件都必须有一个触发器，并且它可以有 0...N 个参数(取决于事件的类型，但是现在不重要。一个触发器也可以是一个参数。显然，在这种情况下，我们可以有一个具有一个触发器和 3 个参数(其中一个是第二个触发器)的事件

我们的事件空间如下(Trigger[Arguments]，+表示新事件):

X1[] + X2[]
X1[Y1] + X2[]
X1[Y2] + X2[]
X1[] + X2[Y1]
X1[] + X2[Y2]
X1[Y1] + X2[Y2]
X1[Y2] + X2[Y1]
X1[X2]
X1[X2,Y1]
X1[X2,Y2]
X1[X2,Y1,Y2]
X2[X1]
X2[X1,Y1]
X2[X1,Y2]
X2[X1,Y1,Y2]

我很确定这就是所有组合。

更新:在对这个问题进行了更多思考之后，我对约束和东西有了一些想法:创建“事件”的规则:1)每个触发器都有一个事件，每个事件都必须有一个触发器2) 事件必须有 > 0 个参数3) 事件不能共享参数4) 触发器可以作为参数

对于暴力解决方案，也许可以生成触发器 + 事件的所有排列，然后消除不符合上述 4 条规则的结果，并将排序视为事件分组？

感谢任何问题名称或想法!

Answer 1

算法:

For all nonempty subsets Triggers of X:
    For all maps from (X \ Triggers) to X:
        For all maps from Y to (X union {None}):
            print the combination, where an assignment of y in Y to None means y is omitted

在 Python 中:

def assignments(xs, ys):
    asgns = [[]]
    for x in xs:
        asgns1 = []
        for y in ys:
            for asgn in asgns:
                asgn1 = asgn[:]
                asgn1.append((x, y))
                asgns1.append(asgn1)
        asgns = asgns1
    return asgns

def combinations(xs, ys):
    xroleasgns = assignments(xs, ('argument', 'trigger'))
    for xroleasgn in xroleasgns:
        triggers = [x for (x, role) in xroleasgn if role == 'trigger']
        if (xs or ys) and not triggers:
            continue
        xargs = [x for (x, role) in xroleasgn if role == 'argument']
        for xargasgn in assignments(xargs, triggers):
            for yargasgn in assignments(ys, [None] + triggers):
                d = dict((x, []) for x in triggers)
                for xarg, t in xargasgn:
                    d[t].append(xarg)
                for yarg, t in yargasgn:
                    if t is not None:
                        d[t].append(yarg)
                print ' + '.join('%s[%s]' % (t, ','.join(args)) for (t, args) in d.iteritems())


"""
>>> assign.combinations(['X1','X2'],['Y1','Y2'])
X1[X2]
X1[X2,Y1]
X1[X2,Y2]
X1[X2,Y1,Y2]
X2[X1]
X2[X1,Y1]
X2[X1,Y2]
X2[X1,Y1,Y2]
X2[] + X1[]
X2[] + X1[Y1]
X2[Y1] + X1[]
X2[] + X1[Y2]
X2[] + X1[Y1,Y2]
X2[Y1] + X1[Y2]
X2[Y2] + X1[]
X2[Y2] + X1[Y1]
X2[Y1,Y2] + X1[]


"""