Algoritmo para obtener cada subconjunto posible de una lista, en orden de su producto, sin construir y clasificar la lista completa (es decir, los generadores)

En la práctica, tengo un conjunto de objetos con probabilidades, y quiero ver cada grupo posible de ellos, en función de la probabilidad de que todos sean verdaderos, asumiendo que son independientes, es decir, en orden descendente de el producto de los elementos de los subconjuntos, o en orden de longitud si las probabilidades son las mismas (de modo que (1, 0.5) viene después de (0.5)).

Ejemplo: Si tengo [ 1, 0.5, 0.1 ] quiero [ (), (1), (0.5), (1, 0.5), (0.1), (1, 0.1), (0.5, 0.1), (1, 0.5, 0.1) ]

En esencia, esto significa que quiero recorrer el conjunto de elementos de un conjunto de elementos en orden, y podría fácilmente generar esto, ordenarlo y terminar. Sin embargo, los conjuntos de poder se vuelven bastante grandes bastante rápido, supongo que normalmente querré uno de los primeros subconjuntos, y prefiero no generar una lista de miles de subconjuntos, ordenarlos y luego nunca mirar más allá del tercero. ¡Aquí es donde los generadores de python esperan salvar el día!

Especificación más formal del problema, necesito encontrar una manera de hacerlo sorted(powerset(input), key = lambda l : reduce (lambda (p, n), e: (p * e, n-1), l, (1, 0)), reverse=True) , como un generador, o de alguna otra manera que me permita evitar la creación y clasificación de toda la lista.

Estoy razonablemente seguro de que esto está relacionado con el problema de la mochila, junto con el problema del producto del subconjunto, pero realmente estoy luchando para obtener un buen algoritmo que funcione, y la ayuda sería muy apreciada :-). No es un problema para que sea más lento que comstackr y clasificar todo en el peor de los casos (iterando hasta el final), solo necesita un rendimiento mucho mejor en el mejor de los casos (dentro del primer 10%, por ejemplo).

    Buena pregunta, fue bastante difícil de resolver. Tampoco se me ocurre una manera de generar las combinaciones en orden, pero uso el poderoso heapq (también conocido como una cola de prioridad) para mantener ordenados a los candidatos.

     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))