Was Algorithmus kann die Potenzmenge eines gegebenen Satzes berechnen?

Question

würde Ich mag effizient eine eindeutige Liste von Kombinationen von Zahlen auf einer Start Liste von Zahlen zu generieren.

Beispiel Anfang list = [1,2,3,4,5] aber der Algorithmus sollte für [1,2,3...n] arbeiten

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]

Hinweis. Ich will nicht, doppelte Kombinationen, auch wenn ich mit ihnen, zum Beispiel in dem obigen Beispiel leben kann ich wirklich nicht die Kombination brauche [1,3,2], weil sie bereits als [1,2,3]

Answer 1

Es ist ein Name für das, was Sie fragen. Es ist die Potenzmenge genannt.

Googeln für "Power-Set-Algorithmus" führte mich zu diesem rekursive Lösung .

Ruby-Algorithmus

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

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

Power Set Intuition

Wenn S = (a, b, c) dann die Powerset (S) ist die Menge aller Teilmengen Powerset (S) = {(), (a), (b), (c), (a, b), (a, c), (b, c), (a, b , c)}

Der erste "Trick" ist zu versuchen definieren rekursiv.

Was für einen Stoppzustand sein würde?

S = () hat das, was Powerset (S)?

Wie erhalten , um es?

durch ein Element gesetzt Reduce

Betrachten wir ein Element herauszunehmen - in dem obigen Beispiel nehmen {c}

S = (a, b) dann Powerset (S) = {(), (a), (b), (a, b)}

Was fehlt?

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

hmmm

Beachten Sie Ähnlichkeiten? Schauen Sie noch einmal ...

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

nimmt jedes Element aus

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

Powerset (S - {c}) = {(), (a), (b), (a, b)} unioned mit

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

wobei e _i ist ein Element von S (a Singleton)

Pseudo-Algorithmus

1. Ist der Satz leer übergeben? Fertig (Beachten Sie, dass Potenzmenge von {} ist {{}})
2. Falls nicht, nehmen Sie ein Element aus
   • rekursiv Call-Methode auf dem Rest des Satzes
   • Rückkehr der Set bestehend aus der Union
     1. die Powerset des Satzes ohne das Element (aus dem rekursiven Aufruf)
     2. Diese gleichen Satz (d.h. 2.1 ), aber mit jedem Element darin unioned mit dem Element zunächst entnommen

Answer 2

Zählen Sie 0 zu 2^n - 1 und drucken Sie die Zahlen nach der binären Darstellung Ihrer Zählung. ein 1 Mittel Sie diese Zahl drucken und ein 0 Mittel nicht. Beispiel:

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

Wie bei hobodave Antwort, sondern iterativ und schneller (in Ruby). Es funktioniert auch mit beiden Array und 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

In meinen Tests IVlad Methode so gut nicht in Ruby arbeiten.

Answer 5

Aus einem Kommentar von OP (Kopie bearbeitet):

Das Beispiel vereinfacht Form von dem, was ich eigentlich tue. Die Zahlen sind Objekte, die eine Eigenschaft „Menge“ haben, möchte ich die Mengen summieren für jede mögliche Kombination dann die Kombination gewählt, die die meisten Objekte verwendet, wobei die Summe der Mengen N innerhalb einiger anderer Grenzen ist, zB x < N < y.

Was Sie haben, ist ein Optimierungsproblem. Was Sie angenommen haben, ist, dass der richtige Weg, um dieses Optimierungsproblem zu nähern ist es in eine Aufzählung Problem zu zersetzen (das ist, was Sie gefragt) und dann ein Filtrationsproblem (die vermutlich Sie wissen, wie zu tun).

Was Sie tun, ist noch nicht erkennen, dass diese Art der Lösung funktioniert nur, entweder (a) für die theoretische Analyse, oder (b) für sehr kleine Werte von n. Die Aufzählung nach dem Sie fragen, ist exponentiell in n, das heißt, Sie am Ende mit etwas würden, die viel zu lange dauern würden in der Praxis auszuführen.

Daher herauszufinden, wie Ihr Optimierungsproblem als solches zu stellen, schreiben Sie eine neue Frage und bearbeiten diese zu Punkt zu.

Answer 6

rekursive und iterative Lösungen Potenzmenge in Schema zu berechnen. Nicht vollständig getestet, obwohl

(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

Im Folgenden ist eine rekursive Lösung, die bereits gebucht sehr ähnlich ist. Einige Behauptungen bieten als eine Art von Einheitstests. Ich habe nicht zu verwenden, „set“ Typ für die Darstellung Satz von Sätzen Python verwaltet. Python sagte, dass "Set-Objekte sind unhashable", wenn Ausdruck versuchen, wie "s.add (set ())".

Siehe auch Lösungen in vielen Programmiersprachen unter 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)