Algoritmo para calcular o conjunto de potência (todos os subconjuntos possíveis) de um conjunto em R
Não consegui encontrar uma resposta para isso em nenhum lugar, então aqui está minha solução.
A questão é: como você pode calcular um conjunto de energia em R?
É possível fazer isso com a biblioteca "sets", com o comando2^as.set(c(1,2,3,4))
, que produz a saída{{}, {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}}
. No entanto, isso usa um algoritmo recursivo, que é bastante lento.
Aqui está o algoritmo que eu criei.
Não é recursivo, então é muito mais rápido do que algumas das outras soluções disponíveis (e 100 vezes mais rápido na minha máquina do que o algoritmo no pacote "sets"). A velocidade ainda é O (2 ^ n).
A base conceitual para esse algoritmo é a seguinte:
for each element in the set:
for each subset constructed so far:
new subset = (subset + element)
Aqui está o código R:
EDIT: aqui está uma versão um pouco mais rápida do mesmo conceito; meu algoritmo original está no terceiro comentário deste post. Este é 30% mais rápido na minha máquina para um conjunto de comprimento 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)
}
Essa versão economiza tempo iniciando o vetor com seu comprimento final no início e acompanhando a variável "contador" da posição na qual salvar novos subconjuntos. Também é possível calcular a posição analiticamente, mas isso foi um pouco mais lento.