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

Question

Je voudrais générer efficacement une liste unique de combinaisons de numéros sur la base d'une liste à partir de chiffres.

exemple début list = [1,2,3,4,5] mais l'algorithme devrait fonctionner pour [1,2,3...n]

result = 

[1],[2],[3],[4],[5]
[1,2],[1,3],[1,4],[1,5]
[1,2,3],[1,2,4],[1,2,5]
[1,3,4],[1,3,5],[1,4,5]
[2,3],[2,4],[2,5]
[2,3,4],[2,3,5]
[3,4],[3,5]
[3,4,5]
[4,5]

Note. Je ne veux pas des combinaisons en double, même si je pouvais vivre avec eux, par exemple, dans l'exemple ci-dessus, je ne vois vraiment pas besoin de la combinaison [1,3,2] parce qu'il a déjà présent comme [1,2,3]

Answer 1

Il y a un nom pour ce que vous demandez. Il est appelé puissance jeu .

recherche sur Google pour "algorithme de jeu de puissance" m'a conduit à cette solution récursive .

Ruby algorithme

def powerset!(set)
   return [set] if set.empty?

   p = set.pop
   subset = powerset!(set)  
   subset | subset.map { |x| x | [p] }
end

Alimentation Set Intuition

Si S = (a, b, c), le powerset (S) est l'ensemble des parties powerset (S) = {(), (a), (b), (c), (a, b), (a, c), (b, c), (a, b , c)}

Le premier "truc" est d'essayer de Define récursive.

Quelle serait un état d'arrêt?

S = () a ce que powerset (S)?

Comment get pour elle?

Réduire fixé par un élément

Envisagez de prendre un élément hors - dans l'exemple ci-dessus, prendre {c}

S = (a, b) puis powerset (S) = {(), (a), (b), (a, b)}

Qu'est-ce qui manque?

powerset (S) = {(c), (a, c), (b, c), (a, b, c)}

hmmm

Avis des similitudes? Regardez à nouveau ...

powerset (S) = {(), (a), (b), (c), (a, b), (a, c), (b, c), ( a, b, c)}

prendre tout élément sur

powerset (S) = {(), (a), (b), (c), (a, b), (a, c), (b, c), ( a, b, c)} is

powerset (S - {c}) = {(), (a), (b), (a, b)} filles fusionnées avec

{c} U powerset (S - {c}) = {(c), (a, c), (b, c), (a, b, c)}

powerset (S) = powerset (S - {e _i }) U ({e _i } U powerset (S - {e _i }))

où e _i est un élément de S (a singleton)

Pseudo-algorithme

1. L'ensemble passe vide? Fait (Remarquer que le pouvoir de {} est {{}})
2. Dans le cas contraire, prendre un élément sur
   • méthode d'appel récursive sur le reste de l'ensemble
   • retourner l'ensemble composé de l'Union des
     1. la powerset de l'ensemble sans l'élément (de l'appel récursif)
     2. ce même ensemble (à savoir, 2,1 ), mais avec chacun des éléments qui y sont filles fusionnées avec l'élément initialement prélevé

Answer 2

Il suffit de compter 0 à 2^n - 1 et imprimer les numéros en fonction de la représentation binaire de votre compteur. un moyen de 1 vous imprimez ce numéro et un moyen de 0 vous n'avez 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}

Answer 3

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

Answer 4

Comme la réponse de hobodave, mais itérative et plus rapide (en Ruby). 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 de IVlad ne fonctionne pas si bien dans Ruby.

Answer 5

D'un commentaire par OP (copie modifiée):

  

L'exemple est une forme simplifiée de ce que je suis en train de faire. Les chiffres sont des objets qui ont une propriété « Quantité », je veux résumer les quantités pour toutes les combinaisons possibles, puis a choisi la combinaison qui utilise le plus d'objets où la somme des N quantités est à l'intérieur d'autres limites, par exemple x < N < y.

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

Ce que vous faites pas encore comprendre est que ce genre de solution ne fonctionne que (a) pour l'analyse théorique, ou (b) pour des valeurs très faibles de n. L'énumération que vous demandez est exponentielle n, qui signifie que vous finiriez avec quelque chose qui prendrait beaucoup trop de temps à courir dans la pratique.

Par conséquent, figure comment poser votre problème d'optimisation en tant que telle, écrire une nouvelle question, et de modifier celui-ci au point de lui.

Answer 6

récursive et solutions itératives pour calculer ensemble de puissance dans le schéma. Pas entièrement testé si

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

Answer 7

Au-delà est une solution récursive, qui est similaire à ceux déjà affichés. Quelques affirmations fournissent comme une sorte de tests unitaires. Je ne l'ai pas réussi à utiliser « set » de type Python pour représenter ensemble des ensembles. Python a dit que "les objets sont ensemble unhashable" en essayant d'expression comme "s.add (set ())".

Voir aussi des 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)