An algorithm for obtaining all possible subsets of a list in the order of their product without creating and sorting the entire list (for example, generators)

Question

In practice, I have a set of objects with probabilities, and I want to look at each possible group of them, with how likely they are all true, assuming that they are independent, i.e. in descending order of the product of the elements of the subsets - or in order of length if the probabilities are the same (so that (1, 0.5) comes after (0.5)).

Example: If I have [ 1, 0.5, 0.1 ] , I want [ (), (1), (0.5), (1, 0.5), (0.1), (1, 0.1), (0.5, 0.1), (1, 0.5, 0.1) ]

In essence, this means that I want to iterate over a set of elements in a set of elements in order, and I could easily generate this, sort it, and do it. However, powerets get pretty fast pretty fast, I expect that I usually want one of the first subsets, and I would prefer not to generate a list of thousands of subsets, sort them, and then never look after the third. This is where python generators hope to save the day!

A more formal specification of the problem, I need to develop a way to do sorted(powerset(input), key = lambda l : reduce (lambda (p, n), e: (p * e, n-1), l, (1, 0)), reverse=True) , as a generator, or in some other way that allows me not to create and sort the entire list.

I am sure that this is due to the knapsack problem as well as the subset product problem, but I am really trying to get a good algorithm for this and the help would be very much appreciated :-). This is not a problem in order to be slower than building + sorting everything in the worst case (iterating everything to the end), it just needs a much better better option (within the first 10%, say) of performance.

Answer 1

Good question, it was pretty hard to solve. I also can’t think of a way to generate combinations, but I can use the powerful heapq (aka priority queue) to sort the candidates.

 from heapq import heappush, heappop import operator def prob(ps): """ returns the probability that *not* all ps are True """ return 1-reduce(operator.mul, ps) def gen(ps): # turn each to a tuple items = ((x,) for x in sorted(ps, reverse=True)) # create a priority queue, sorted by probability pq = [(prob(x),x) for x in items] # because you wanted this yield () # as long as there are valid combinations while pq: # get the best un-yielded combination, the pq makes sure of that p, x = heappop(pq) yield x # generate all the combinations from this item for other in ps: # keeping the tuples sorted -> unique combinations if other < x[-1]: # create a new combination new = x+(other,) item = prob(new), new # add it to the queue heappush(pq,item) a = [1, 0.1, 0.5] print list(gen(a))