Bademeister: Rekursive Array-Abfrage

Beitrag lesen

Hi.

Das Ganze wird vermutlich nur rekursiv funktionieren - aber ich komme zu keiner Lösung.

Die Potenzmenge einer Menge {a_1, ..., a_n} kriegst Du rekursiv wie folgt:

Jedes Element der Potenzmenge enthält entweder a_n, oder es enthält es nicht. (Wärste jetzt nicht drauf gekommen, was? ;-)) Nimm also die Potenzmenge von {a_1, ..., a_(n-1)}. Davon zwei Kopien, und zu jedem Element einer der Kopien tust Du a_n dazu.

Was willst Du denn eigentlich als Antwort genau für ein Datum kriegen: Ein Array, das aus allen Teil-Arrays besteht? Dann wäre der rekursive Ansatz:

  
function getPowerSet($array) {  
  
    // Falls $array leer ist, gib ein leeres Array zurück. Ist ja  
    // immer gut, wenn Rekursionen nicht endlos laufen.  
       if (!count($array)) return array(); // und Achtung: [link:http://de.wikipedia.org/wiki/GIGO@title=GIGO]  
  
    // Letztes Element separieren:  
       $lastElement = array_pop($array);  
  
    // Potenzmenge des verkürzten Arrays bilden:  
       $subPowerSet = getPowerSet($array);  
  
    /* Und nun den schlauen Trick von oben: zwei Kopien davon  
       nehmen und an [link:http://uk.php.net/manual/de/function.array-map.php@title=jedes Element] einer der Kopien $lastElement  
       [link:http://uk.php.net/manual/de/function.array-push.php@title=dranklatschen]. Dann die beiden Array [link:http://uk.php.net/manual/de/function.array-merge.php@title=zusammenfügen] und zurückgeben.  
    */  
  
}  

Macht das Sinn?

Viele Grüße,
der Bademeister