Combinations with multiple containers of varying sizes

If you know what this kind of problem is called, let me know (unless you actually know the answer to the question).

If I have a set Z of objects, is there an algorithm for diving them up between a bunch of containers (each holding a certain number of objects)?

To slightly complicate the problem, let's assume the set of objects we start with has a subset X. There are X containers, and each container must hold a single element of X, in addition to other objects (if it has room).

The best way I can think of doing this currently is looking at the disjunction of Z and X, let's call it Y. Then we can generate the z choose x combinations, and then expand that out for all possi开发者_开发知识库ble combinations of x.

Example: The actual problem is basically generating all events in a space. Suppose we have two event triggers (X) and 2 event arguments (Y), where Z = X U Y. Each event must have a trigger, and it can have 0...N arguments (depending on the type of event, but that isn't important for now. A trigger can also be an argument. Clearly, in this situation we can have a single event with one trigger and 3 arguments (one of which is the second trigger)

Our event space is as follows (Trigger[Arguments], + indicates a new event):

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]

I'm pretty sure that's all the combinations.

Update: After thinking a bit more about the problem, I have a few thoughts on constraints and stuff: Rules for creating "events": 1) There is an event for every trigger, and every event must have a trigger 2) Event must have > 0 arguments 3) Events cannot share arguments 4) Triggers can be used as arguments

For a brute force solution, perhaps one could generate all permutations of the triggers + events and then eliminate results that don't match the above 4 rules, and treat the ordering as grouping of events?

Thanks for any problem names or ideas!

Algorithm:

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

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


"""

Here is my java implementation over9000's solution to the original problem:

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;
}