与多个不同尺寸的容器的组合

Question

如果您知道此类问题的名称，请告诉我（除非您确实知道问题的答案）。

如果我有一组 Z 个对象，是否有一种算法可以将它们分配到一堆容器（每个容器包含一定数量的对象）之间？

让问题稍微复杂一些，让我们假设我们开始的对象集有一个子集 X。有 X 个容器，每个容器除了其他对象（如果有空间）之外，还必须容纳 X 的单个元素。

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

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

我们的事件空间如下（触发器[）。参数]，+ 表示新事件）：

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


"""

Answer 2

这是我的 java 实现 over9000 对原始问题的解决方案：

public static void main(String[] args) throws Exception {
    ArrayList xs = new ArrayList();
    ArrayList ys = new ArrayList();
    xs.add("X1");
    xs.add("X2");
    ys.add("Y1");
    ys.add("Y2");

    combinations(xs,ys);
}

private static void combinations(ArrayList xs, ArrayList ys) {
    ArrayList def = new ArrayList();
    def.add("argument");
    def.add("trigger");

    ArrayList<ArrayList> xroleasgns = assignments(xs, def);
    for(ArrayList xroleasgn:xroleasgns){
        // create triggers list
        ArrayList triggers = new ArrayList();
        for(Object o:xroleasgn){
            Pair p = (Pair)o;
            if("trigger".equals(p.b.toString()))
                triggers.add(p.a);              
        }

        if((xs.size()>0 || ys.size()>0) && triggers.size()==0)
            continue;

        // create xargs list
        ArrayList xargs = new ArrayList();
        for(Object o:xroleasgn){
            Pair p = (Pair)o;
            if("argument".equals(p.b.toString()))
                xargs.add(p.a);             
        }

        // Get combinations!
        for(ArrayList xargasgn:assignments(xargs,triggers)){
            ArrayList yTriggers = new ArrayList(triggers);
            yTriggers.add(null);

            for(ArrayList yargasgn:assignments(ys,yTriggers)){

                // d = dict((x, []) for x in triggers)
                HashMap<Object,ArrayList> d = new HashMap<Object,ArrayList>();
                for(Object x:triggers)
                    d.put(x, new ArrayList());

                for(Object o:xargasgn){
                    Pair p = (Pair)o;
                    d.get(p.b).add(p.a);    
                }

                for(Object o:yargasgn){
                    Pair p = (Pair)o;
                    if(p.b!=null){
                        d.get(p.b).add(p.a);
                    }
                }


                for(Entry<Object, ArrayList> e:d.entrySet()){
                    Object t = e.getKey();
                    ArrayList args = e.getValue();
                    System.out.print(t+"["+args.toString()+"]"+"+");
                }
                System.out.println();                   

            }
        }
    }
}

private static ArrayList<ArrayList> assignments(ArrayList xs, ArrayList def) {
    ArrayList<ArrayList> asgns = new ArrayList<ArrayList>();
    asgns.add(new ArrayList()); //put an initial empty arraylist
    for(Object x:xs){
        ArrayList asgns1 = new ArrayList();
        for(Object y:def){
            for(ArrayList<Object> asgn:asgns){
                ArrayList asgn1 = new ArrayList();
                asgn1.addAll(asgn);
                asgn1.add(new Pair(x,y));
                asgns1.add(asgn1);
            }
        }
        asgns = asgns1;
    }
    return asgns;
}