La génération de puissance définie de manière récursive, sans boucles

L'ensemble des parties de abcd est l'union de la puissance-ensembles de abc, abd, acd (plus abcd lui-même*).

 P(`abcd`) = {`abcd`} + P(`abc`) + P(`abd`) + P(`acd`) + P(`bcd`)

_{* à Noter que la ensemble vide, qui est un membre de P(abcd) est également un membre de P(abc), P(abd), ... de sorte que l'équivalence est indiqué ci-dessus tient.}

De manière récursive, P(abc) = {abc} + P(ab) + P(ac), et ainsi de suite

Une première approche, en pseudo-code, pourrait être:

powerset(string) {
  add string to set;
  for each char in string {
   let substring = string excluding char,
   add powerset(substring) to set
  }
  return set;      
}

La récursivité se termine lorsque la chaîne est vide (car il ne pénètre jamais dans la boucle).

Si votre voulez vraiment pas boucles, vous devez la convertir en boucle à l'autre de la récursivité.
Maintenant, nous voulons générer ab, ac et cb de abc

powerset(string) {
  add string to set;
  add powerset2(string,0) to set;
  return set
}

powerset2(string,pos) {
  if pos<length(string) then
    let substring = (string excluding the char at pos)
    add powerset(substring) to set
    add powerset2(string,pos+1) to set
  else 
    add "" to set
  endif
  return set
}

Une autre approche mettre en œuvre une fonction récursive P qui supprime le premier caractère de son argument, ou ne l'est pas. (Ici + moyens mis de l'union, . moyens de concaténation et λ est la chaîne vide)

P(abcd) = P(bcd) + a.P(bcd)
P(bcd)  = P(cd)  + b.P(cd)
P(cd)   = P(d)   + c.P(d)
P(d)    = λ+d //particular case

Puis

P(d)    = λ+d
R(cd)   = P(d)  + c.P(d)  = λ + d + c.(λ+d) = λ + d + c + cd
R(bcd)  = P(cd) + b.P(cd) = λ + d + c + cd + b.(λ + d + c + cd)
                          = λ + d + c + cd + b + bd + bc + bcd
P(abcd) =  λ +  d +  c +  cd +  b +  bd +  bc +  bcd 
        + aλ + ad + ac + acd + ab + abd + abc + abcd 

Si les boucles ont été autorisées, P est de puissance-fonction set. Sinon, nous aurions besoin d'un paramètre loopless fonction de la concaténation d'un personnage donné à un ensemble de chaînes de caractères (qui sont de toute évidence deux choses).

Certains tweak pourrait être possible en jouant avec String.replace (si un String résultat est souhaitée, ou par le remplacement de Set avec List (de sorte que les "autres" paramètre est en fait le premier élément dans la liste).

Eh bien, si vous n'avez pas de boucles, d'émuler un avec la récursivité, à l'aide des itérateurs c'est acutally assez simple.

    public final Set<Set<Integer>> powerSet(Set<Integer> set) {
        Set<Set<Integer>> powerSet = new HashSet<>();
        powerSet(set, powerSet, set.iterator());
        return powerSet;
    }
    public final void powerSet(Set<Integer> set, Set<Set<Integer>> powerSet, Iterator<Integer> iterator) {
        if(iterator.hasNext()) {
            Integer exlude = iterator.next();
            Set<Integer> powThis = new HashSet<Integer>();
            powThis.addAll(set);
            powThis.remove(exlude);
            powerSet.add(powThis);
            powerSet(powThis, powerSet, powThis.iterator());
            powerSet(set, powerSet, iterator);
        }
    }
//usage
        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        log.error(powerSet(set).toString());

void powerSet(int * ar, int *temp, int n, int level,int index)
{
    if(index==n) return;

    int i,j;
    for(i=index;i<n;i++)
    {
    temp[level]=ar[i];

    for(j=0;j<=level;j++)
    printf("%d ",temp[j]);
    printf("   - - -  t\n");

    powerSet(ar, temp, n, level+1,i+1);
    }
}

int main()
{
    int price[] = {1,2,3,7};
    int temp[4] ={0};

    int n = sizeof(price)/sizeof(price[0]);

    powerSet(price, temp, n, 0,0);


    return 0;
}

Juste pour le fun, une version qui ne powersets de toute valeur stockée dans un LinkedList (pour le rendre facile pour supprimer l'élément de tête). Java 8 ruisseaux faire la partie fonctionnelle:

static <T> LinkedList<LinkedList<T>> powerset(LinkedList<T> elements) {
  if (elements.isEmpty()) 
    return copyWithAddedElement(new LinkedList<>(), new LinkedList<>());
  T first = elements.pop();
  LinkedList<LinkedList<T>> powersetOfRest = powerset(elements);
  return Stream.concat(
      powersetOfRest.stream(), 
      powersetOfRest.stream().map(list -> copyWithAddedElement(list, first)))
          .collect(Collectors.toCollection(LinkedList::new));
}

static <T> LinkedList<T> copyWithAddedElement(LinkedList<T> list, T elt) {
  list = new LinkedList<>(list);
  list.push(elt);
  return list;
}

C'est inspiré par ce qui suit Common Lisp, ce qui montre que la langue peut rendre les choses plus simples:

(defun powerset (set)
  (cond ((null set) '(()))
        (t (let ((powerset-of-rest (powerset (cdr set))))
          (append powerset-of-rest
                  (mapcar #'(lambda (x) (cons (car set) x)) 
                          powerset-of-rest))))))