Anonymous user
Power set: Difference between revisions
→{{header|R}}: added non-recursive method that is 100x faster
(Updated first D entry, + second D entry) |
(→{{header|R}}: added non-recursive method that is 100x faster) |
||
Line 1,697:
=={{header|R}}==
===Non-recursive version===
The conceptual basis for this algorithm is the following:
<lang>for each element in the set:
for each subset constructed so far:
new subset = (subset + element)
</lang>
Even though the method is not recursive, the speed of the algorithm is still O(n^2).
The code is optimized to reduce the creation of new lists, which is a slow step. (You algorithm is a couple lines shorter without "temp", but takes ~4x as long).
<lang R>powerset = function(set){
ps = list()
ps[[1]] = numeric() #Start with the empty set.
for(element in set){ #For each element in the set, take all subsets
temp = vector(mode="list",length=length(ps)) #currently in "ps" and create new subsets (in "temp")
for(subset in 1:length(ps)){ #by adding "element" to each of them.
temp[[subset]] = c(ps[[subset]],element)
}
ps=c(ps,temp) #Add the additional subsets ("temp") to "ps".
}
return(ps)
}
powerset(1:4)
</lang>
===Recursive version===
{{libheader|sets}}
The sets package includes a recursive method to calculate the power set. However, this method takes ~100 times longer than the non-recursive method above.
<lang R>library(sets)</lang>
An example with a vector.
| |||