Алгоритм расчета мощности

Question

Я только что обнаружил алгоритм поиска набора мощности. Я гуглил после решений, но не нашел ни одного, который сработал бы хорошо, поэтому сам придумал. Но мне интересно, что это за алгоритм, потому что я не могу найти его в сети или в каких-либо книгах. Я имею в виду, у него есть имя? По сравнению с алгоритмами, которые я нашел на некоторых сайтах для расчета мощности, я думаю, что мой намного лучше, и удивляюсь, почему никто не использует его?

Это алгоритм:

R <- []
L <- [ e1, e2 ... en ]
c <- 0
function: powerSet(L, c)
  R <- R union L
  for e in L starting at c
    powerSet(L\{e}, c)
  end
  return R
end

А вот это реализовано на Java:

public static void powerSet(List<String> list, int count)
{
  result.add(list);

  for(int i = count; i < list.size(); i++)
  {
    List<String> temp = new ArrayList<String>(list);
    temp.remove(i);

    powerSet(temp, i);
  }
}

Answer 1

Взгляните на страницу Rosetta Code Power Set . Там есть несколько реализаций рекурсивных решений (в том числе Java). В общем, рекурсивное решение подразумевает невероятно большой стек вызовов, который замедляет работу.

Answer 2

В основном по двум причинам:

1. Используются глобальные переменные;
2. Это рекурсивно, хотя на самом деле это не имеет большого значения, потому что это алгоритм O(2^n).

Answer 3

public final static Set<Set<Character>> powerSet(Set<Character> s){
    Set<Set<Character>> result = new HashSet<Set<Character>>();
    result.add(s);
    for (Character c:s){
        Set<Character> subSet = new HashSet<Character>(s);
        subSet.remove(c);
        result.addAll(powerSet(subSet));
    }
    return result;
}