Алгоритм расчета мощности набора (все возможные подмножества) множества в R
Я нигде не мог найти ответ на этот вопрос, так что вот мое решение.
Вопрос в том, как рассчитать мощность в R?
Это можно сделать с помощью библиотеки «наборы», с помощью команды2^as.set(c(1,2,3,4))
, который дает выход{{}, {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}}
, Однако для этого используется рекурсивный алгоритм, который довольно медленный.
Вот алгоритм, который я придумал.
Он не рекурсивный, поэтому он намного быстрее, чем некоторые другие решения (и примерно в 100 раз быстрее на моем компьютере, чем алгоритм в пакете "sets"). Скорость все еще O (2 ^ n).
Концептуальной основой этого алгоритма является следующее:
for each element in the set:
for each subset constructed so far:
new subset = (subset + element)
Вот код R:
РЕДАКТИРОВАТЬ: вот несколько более быстрая версия той же концепции; Мой оригинальный алгоритм в третьем комментарии к этому посту. Этот на 30% быстрее на моей машине для набора длины 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)
}
Эта версия экономит время, инициируя вектор с его окончательной длиной в начале и отслеживая с помощью переменной "counter" позиции, в которой сохраняются новые подмножества. Также возможно рассчитать позицию аналитически, но это было немного медленнее.