Algorithme de calcul de l'ensemble de puissance

Je viens de découvrir un algorithme pour trouver l'ensemble de puissance. J'ai cherché des solutions, mais je n'en ai trouvé aucune qui fonctionne, alors j'en ai trouvé une moi-même. Mais je me demande quel algorithme c'est, parce que je ne peux pas le trouver sur le net ou dans tous les livres. Je veux dire, a-t-il un nom? Comparé aux algorithmes que j'ai trouvés sur certains sites pour calculer la puissance, je pense que le mien est bien meilleur et je me demande pourquoi personne ne l'utilise?Algorithme de calcul de l'ensemble de puissance

C'est l'algorithme:

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

Et ici, il est implémenté en 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); 
    } 
}

Source

2009-09-14 rejeep

Principalement pour deux raisons:

Il utilise des variables globales ;
Il est récursif, même si cela n'a pas beaucoup d'importance car c'est un algorithme O(2^n).

Source

2009-09-14 16:42:17

+1. Il ajoute également des ensembles vides pour chaque élément de l'ensemble d'origine. – ChssPly76

J'aurais dû préciser que je ne faisais que comparer mon algorithme à d'autres algorithmes O (2^n). Je sais que c'est terriblement lent. Je suis venu avec l'algorithme parce que nous avions mission à l'école pour créer un algorithme de force brute. Mais pour être un algorithme de force brute, je pense que le mien est vraiment sympa. Je ne vois pas vraiment pourquoi ce serait un problème d'utiliser une variable globale. Et dans de nombreux cas, vous ne stockez pas l'ensemble dans un résultat, mais effectuez une action sur l'ensemble à la place. ChssPly76, Il ajoute seulement un ensemble vide et c'est l'ensemble vide. Le résultat de l'algorithme est la puissance, rien d'autre. – rejeep

Un ensemble de puissance se compose de 2^n éléments, il s'ensuit qu'un algorithme doit être au moins 'O (2^n)' sauf si j'ai terriblement tort. @rejeep – phant0m

Jetez un oeil à la page Rosetta Code Power Set. Il y a quelques implémentations de solutions récursives (y compris Java). En général, cependant, une solution récursive implique une pile d'appels incroyablement grande qui ralentit les choses.

Source

2009-09-15 10:58:46

Lien vraiment cool! –

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; 
}

Source

2011-03-11 12:07:56

-1: Pour raviver un thread mort avec un code inefficace :-) C'est Omega (n!). Pas O (2^n). –

Algorithme de calcul de l'ensemble de puissance

Répondre

Questions connexes