Algorytm obliczania zestawu mocy (wszystkie możliwe podzbiory) zestawu w R
Nigdzie nie mogłem znaleźć odpowiedzi na to pytanie, więc oto moje rozwiązanie.
Pytanie brzmi: jak obliczyć moc ustawioną w R?
Można to zrobić za pomocą biblioteki „sets” za pomocą polecenia2^as.set(c(1,2,3,4))
, która daje wynik{{}, {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}}
. Jednak wykorzystuje to algorytm rekurencyjny, który jest raczej powolny.
Oto algorytm, który wymyśliłem.
Jest nierekurencyjny, więc jest znacznie szybszy niż niektóre inne rozwiązania (i ~ 100x szybszy na moim komputerze niż algorytm w pakiecie „zestawy”). Prędkość nadal wynosi O (2 ^ n).
Podstawą koncepcyjną tego algorytmu jest:
for each element in the set:
for each subset constructed so far:
new subset = (subset + element)
Oto kod R:
EDYCJA: oto nieco szybsza wersja tej samej koncepcji; mój oryginalny algorytm znajduje się w trzecim komentarzu do tego posta. Ten jest o 30% szybszy na moim komputerze dla zestawu długości 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)
}
Ta wersja oszczędza czas, inicjując wektor o jego końcowej długości na początku i śledząc zmienną „licznika” pozycji, w której należy zapisać nowe podzbiory. Możliwe jest również obliczenie pozycji analitycznie, ale to było nieco wolniejsze.