Algorithmus zur Berechnung der Potenzmenge (alle möglichen Teilmengen) einer Menge in R

Darauf konnte ich nirgendwo eine Antwort finden. Hier ist meine Lösung.

Die Frage ist: Wie kann man eine in R eingestellte Leistung berechnen?

Dies ist mit der Bibliothek "sets" mit dem Befehl möglich2^as.set(c(1,2,3,4)), was die Ausgabe ergibt{{}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}. Dies verwendet jedoch einen rekursiven Algorithmus, der ziemlich langsam ist.

Hier ist der Algorithmus, den ich mir ausgedacht habe.

Es ist nicht rekursiv und daher viel schneller als einige der anderen Lösungen (und ~ 100x schneller auf meinem Computer als der Algorithmus im Paket "sets"). Die Geschwindigkeit ist immer noch O (2 ^ n).

Die konzeptionelle Basis für diesen Algorithmus ist die folgende:

for each element in the set:
    for each subset constructed so far:
        new subset = (subset + element)

Hier ist der R-Code:

EDIT: hier ist eine etwas schnellere Version des gleichen Konzepts; Mein ursprünglicher Algorithmus befindet sich im dritten Kommentar zu diesem Beitrag. Dieser ist 30% schneller auf meiner Maschine für einen Satz von Länge 19.

powerset = function(s){
    len = length(s)
    l = vector(mode="list",length=2^len) ; l[[1]]=numeric()
    counter = 1L
    for(x in 1L:length(s)){
        for(subset in 1L:counter){
            counter=counter+1L
            l[[counter]] = c(l[[subset]],s[x])
        }
    }
    return(l)
}

Diese Version spart Zeit, indem der Vektor mit seiner endgültigen Länge am Anfang initiiert wird und die "Zähler" -Variable der Position verfolgt wird, an der neue Teilmengen gespeichert werden sollen. Es ist auch möglich, die Position analytisch zu berechnen, aber das war etwas langsamer.

Antworten auf die Frage(4)

Ihre Antwort auf die Frage