getting all possible combinations while staying under max constraint

Question

  def pickSubs(self, subjects, maxWork, maxLottery):

    totWork = 0
    totLott = 0
    studentSubs = []
    for s in subjects:
        totWork += s.getWork()
        totLott += s.getLottery()

        if totLott <= maxLottery and totWork <= maxWork:
                studentSubs.append(s)

    return studentSubs

I am trying to use comparators to decide best choices for a student based on different factors.

My issue is I want to append all possible objects 's' if the total work and lottery values are under maxWork, maxLottery but I am not appending all possible combinations. I am just appending until I reach max constraint value

How can I get all possible combinations?

Do the getWork and getLottery methods return different values each time? — chthonicdaemon, May 26 '13 at 18:32
@chthoni yes I am parsing a txt file with many different values. So it is not just combinations but combinations while staying under both maxWork and maxLottery — Padraic Cunningham, May 26 '13 at 18:37
Another question: are these things independent or dependent? In other words, is there a "work" associated with a "lottery" or are can one assign them as separate problems? I would imagine a good place to start would be to have a list of works and lotteries instead of reading them sequentially as you are now. Depending on how many of these things you have, it may also be better to use a MILP solver for this rather than enumerating all the possible combinations. — chthonicdaemon, May 27 '13 at 08:23
Basically each instance 's' is:Course,Value,Work,Lottery. Work is an integer and Lottery is either 1 or 0 where 1 indicates the subject is a lottery and 0 means it is not. So both Work and Lottery values are relevant to whether the subject shall be taken by the student or not. I hope that makes sense. — Padraic Cunningham, May 27 '13 at 09:37
@chthonicdaemon do you have any good link on MILP, I am struggling to find any? — Padraic Cunningham, May 27 '13 at 09:56

chthonicdaemon · Accepted Answer · 2013-05-29T04:37:40.767

This should solve your question as asked:

def pickSubs(self, subjects, maxWork, maxLottery):
    from itertools import chain, combinations

    validcombinations = []

    for comb in chain.from_iterable(combinations(subjects, n) 
                                    for n in range(1, len(subjects)+1):
        sumWork = sum(s.getWork() for s in comb)
        sumLottery = sum(s.getLottery() for s in comb)

        if sumWork <= maxWork and sumLottery <= maxLottery:
            validcombinations.append(comb)
    return validcombinations

But, be aware that this will typically go through an incredibly long list. If you are actually trying to find the "best" selection of subjects which satisfies these criteria, I really recommend you have a look at something like PuLP, where you can set this up as an integer problem using binary choice variables. I think how to do that would require you to ask another question.

Thanks for taking the time to help me on this, I have an issue, the sumWork is returning only one value repeatedly so it never goes past the if statement. — Padraic Cunningham, May 28 '13 at 19:55

getting all possible combinations while staying under max constraint

1 Answers1