Quel algorithme peut calculer l'ensemble de puissance d'un ensemble donné?

count 02^n - 1 et imprimez les nombres selon la représentation binaire de votre compte. 1 signifie que vous imprimez et un 0 signifie que vous ne le faites pas. Exemple:

set is {1, 2, 3, 4, 5}
count from 0 to 31:
count = 00000 => print {}
count = 00001 => print {1} (or 5, the order in which you do it really shouldn't matter)
count = 00010 => print {2}
        00011 => print {1, 2}
        00100 => print {3}
        00101 => print {1, 3}
        00110 => print {2, 3}
        00111 => print {1, 2, 3}
        ...
        11111 => print {1, 2, 3, 4, 5}

def power(a)
 (0..a.size).map {|x| a.combination(x).to_a}.flatten(1)
end

identique à la réponse de hobodave, mais itérative et plus rapide (en rubis). Il fonctionne également avec les deux Array et Set.

def Powerset(set)
    ret = set.class[set.class[]]
    set.each do |s|
        deepcopy = ret.map { |x| set.class.new(x) }
        deepcopy.map { |r| r << s }
        ret = ret + deepcopy
    end
    return ret
end

dans mes tests, la méthode D'IVlad ne fonctionne pas si bien à Ruby.

à Partir d'un commentaire par OP (révisé):

l'exemple est une forme simplifiée de ce que je fais réellement. Les nombres sont des objets qui ont une propriété "Qty", je veux faire la somme des quantités pour chaque combinaison possible puis choisir la combinaison qui utilise le plus d'objets où la somme des quantités N est à l'intérieur de certaines autres limites, e.g.x < N < y.

Ce que vous avez est un problème d'optimisation. Ce que vous avez supposé est que la bonne façon d'aborder ce problème d'optimisation est de le décomposer en une énumération problème (qui est ce que vous avez demandé), puis une filtration problème (qui sans doute vous savez comment le faire).

ce que vous ne réalisez pas encore est que ce genre de solution ne fonctionne que (a) pour l'analyse théorique, ou (b) Pour de très petites valeurs de n. L'énumération que vous demandez est exponentielle dans

par conséquent, trouvez comment poser votre problème d'optimisation en tant que tel, écrivez une nouvelle question, et éditez celle-ci pour y pointer.

Récursive et itérative des solutions pour calculer la puissance en régime. Pas entièrement testé cependant

(define (power_set set)
      (cond 
        ((empty? set) (list '()))
        (else
         (let ((part_res (power_set (cdr set))))
           (append (map (lambda (s) (cons (car set) s)) part_res) part_res)))))

(define (power_set_iter set)
  (let loop ((res '(())) (s set))
    (if (empty? s)
        res
        (loop (append (map (lambda (i) (cons (car s) i)) res) res) (cdr s)))))

Ci-après est une solution récursive, qui est similaire à déjà posté. Quelques assertions fournissent comme genre de tests unitaires. Je n'ai pas réussi à utiliser le type "set" Python pour représenter set of sets. Python a dit que " set objects are unhashable "en essayant des expressions comme" S. add (set ())".

Voir aussi les solutions dans de nombreux langages de programmation à http://rosettacode.org/wiki/Power_set

def generatePowerSet(s, niceSorting = True):
    """Generate power set of a given set.

    The given set, as well as, return set of sets, are implemented
    as lists.

    "niceSorting" optionnaly sorts the powerset by increasing subset size.
    """
    import copy

    def setCmp(a,b):
        """Compare two sets (implemented as lists) for nice sorting"""
        if len(a) < len(b):
            return -1
        elif len(a) > len(b):
            return 1
        else:
            if len(a) == 0:
                return 0
            else:
                if a < b:
                    return -1
                elif a > b:
                    return 1
                else:
                    return 0

    # Initialize the power set "ps" of set "s" as an empty set                    
    ps = list()

    if len(s) == 0:
        ps.append(list())
    else:

        # Generate "psx": the power set of "sx", 
        # which is "s" without a chosen element "x"
        sx = copy.copy(s)
        x = sx.pop()
        psx = generatePowerSet(sx, False)        

        # Include "psx" to "ps"      
        ps.extend(psx)

        # Include to "ps" any set, which contains "x"
        # Such included sets are obtained by adding "x" to any subset of "sx"
        for y in psx:
            yx = copy.copy(y)
            yx.append(x)
            ps.append(yx)

    if niceSorting:
        ps.sort(cmp=setCmp)      

    return ps

assert generatePowerSet([]) == [[]]

assert generatePowerSet(['a']) == [[], ['a']]

assert generatePowerSet(['a', 'b']) == [[], ['a'], ['b'], ['a', 'b']]

assert generatePowerSet(['a', 'b','c']) == [[], 
                                            ['a'], ['b'], ['c'], 
                                            ['a', 'b'], ['a', 'c'], ['b', 'c'],
                                            ['a', 'b', 'c'] ]

assert generatePowerSet(['a', 'b','c'], False) == [ [], 
                                                    ['a'], 
                                                    ['b'], 
                                                    ['a', 'b'], 
                                                    ['c'], 
                                                    ['a', 'c'], 
                                                    ['b', 'c'], 
                                                    ['a', 'b', 'c'] ]

print generatePowerSet(range(4), True)