Na prática, tenho um conjunto de objetos com probabilidades e quero examinar cada grupo possível deles, para determinar a probabilidade de eles seremtudo true assumindo que são independentes - ou seja, em ordem decrescente do produto dos elementos dos subconjuntos - ou em ordem de comprimento, se as probabilidades forem as mesmas (de modo que (1, 0,5) venha depois (0,5)).

Exemplo: se eu tiver[ 1, 0.5, 0.1 ] eu quero[ (), (1), (0.5), (1, 0.5), (0.1), (1, 0.1), (0.5, 0.1), (1, 0.5, 0.1) ]

Em essência, isso significa que eu quero iterar sobre o conjunto de potências de um conjunto de elementos em ordem, e eu poderia facilmente gerar isso, classificá-lo e concluir. No entanto, os conjuntos de potências ficam muito grandes rapidamente, espero que eu queira um dos primeiros subconjuntos e prefiro não gerar uma lista de milhares de subconjuntos, classificá-los e nunca olhar para além do terceiro. É aqui que esperamos que os geradores python salvem o dia!

Especificação mais formal do problema, eu preciso descobrir uma maneira de fazersorted(powerset(input), key = lambda l : reduce (lambda (p, n), e: (p * e, n-1), l, (1, 0)), reverse=True), como gerador, ou de alguma outra maneira que evite criar e classificar a lista inteira.

Estou razoavelmente certo de que isso está relacionado ao problema da mochila, junto com o problema do produto do subconjunto, mas estou realmente lutando para obter um bom algoritmo para ele funcionar, e a ajuda seria muito apreciada :-). Não é um problema ser mais lento do que construir + classificar tudo no pior dos casos (repetindo todo o caminho até o fim), ele só precisa de um melhor desempenho (nos primeiros 10%, por exemplo).