Generating all subsets of a list giving a certain product without iterating over the whole powerset? (Python)

Question

Possible Duplicate:
Finding all possible combinations of numbers to reach a given sum

I don't want to use Itertools because it outputs things in an order I don't want and can't use (I need to be able to evaluate what the combination generator is trying to output to decide if I want to keep going down that branch).

For instance, let's say I have a list [1,2,3,4,5] and I want to output combinations that have a full-product <=12 without wasting iterations. If I generate, say, [1,2,3], this is fine because 1*2*3=6. But if I try [1,2,3,4] then 1*2*3*4=24, and this is greater than 12, and therefore I shouldn't even bother looking into [1,2,3,5] or [1,2,4,5] and so on.

Current attempt:

from operator import mul

mylist=[1,2,3,4,5]
limit=12

def productOK(mylist): #but this can be any conditional, theoretically
    if reduce(mul, mylist) > limit:
        return False
    return True


def generateValidSubsets(mylist):
    for r in range(1,len(mylist)+1):
        start=mylist[:r]
        if productOK(start)==False: break
        #not sure how to recombine in the right order otherwise
        yield start



for combo in generateValidSubsets(mylist):
    print combo

Where am I going wrong?

Yes, but I don't know the right way to recursively split the list apart and look at things in the right order — AOAOne, Apr 18 '12 at 13:59
@Marcin I'm trying to stop early if it's going down a bad path, without skipping over any possible good paths. For instance, in itertools, if I were to break out of a loop early, I would potentially miss other same-length valid combinations just because they start with a higher number — AOAOne, Apr 18 '12 at 14:00
Right now, your question is "Please write this code for me". If you post your current code, and explain the part where you are stuck trying to implement the cut, then it will be a question about implementing the cut. — Marcin, Apr 18 '12 at 14:06
I didn't post the code because it's probably very, very, very wrong. If I knew how to code it, I wouldn't have asked the question, honestly. — AOAOne, Apr 18 '12 at 14:14

Marcin · Answer 1 · 2012-04-18T15:05:28.593

0

I strongly recommend that you switch to a recursive implementation. This will allow you to implement the cuts more easily:

def subs(target, universe, currentsubs, currentproduct, goodsubs):
    first_from_universe_not_in_currentsubs = # an exercise for the reader
    newsubs = [first_from_universe_not_in_currentsubs] + currentsubs
    newproduct = currentproduct * first_from_universe_not_in_currentsubs
    if newproduct == target:
       return goodsubs + [newsubs]
    elif newproduct > target:
       return goodsubs
    else:
       return subs(target, universe, newsubs, newproduct, goodsubs)

subs(12, [1,2,3,4,5], [], 0, [])

Even if you fill in the blank above, it might not be quite right, but it does show you how can implement the cut.

edited Apr 18 '12 at 15:05

answered Apr 18 '12 at 14:27

Marcin

48,559
18
128
201

I don't think this does what I am trying to do (can't tell what most of these variables are intended for), and I don't think "first from universe not in current subs" is particularly efficient if it's needing to rescan the entire list. – AOAOne Apr 18 '12 at 14:35
@AOAOne If you can't be bothered to understand the code, that rather suggests that you are looking for someone to show you teh codez. – Marcin Apr 18 '12 at 14:36
I am saying that I don't think it's doing what I am asking about. Why does it matter if newproduct equals the target? That's not relevant to my question -- I only care if it's greater than. But if it's greater than, you return "goodsubs" (which I assume means "the current good solutions"). Otherwise I am not sure what currentsubs and why it needs "first from universe not in current subs" which again I think is taking the long way around. – AOAOne Apr 18 '12 at 14:39
@AOAOne I don't know what you mean "cut a list". I am showing you how to cut a call graph. – Marcin Apr 18 '12 at 14:59

Generating all subsets of a list giving a certain product without iterating over the whole powerset? (Python)

1 Answers1