Rekursive Array-Abfrage

[Florian]

Hallo Team,

ich brauche eure Hilfe - ich komme leider nicht weiter.

Problemstellung:
Ich habe ein Array, zB array1("a","b","c") oder array2("1","2","3","4")
und nun möchte ich alle einzelnen Werte kombinieren, so dass ich als Ergebnis sämtliche Kombinationsmöglichkeiten erhalte.

D.h
array1 ergibt abc, ab, ac, bc, a, b, c
array2 ergibt 1234, 123, 124, 134, 234, 12, 13, 14, 23, 24, 34, 1, 2, 3, 4

Besondere Herausforderung dabei ist, dass die Anzahl der Werte im Array unterschiedlich sein kann und alle Kombinationen abgedeckt, aber nicht doppelt vorkommen sollen.

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

Gefunden habe ich bisher diesen Ansatz: http://www.php.de/php-fortgeschrittene/18107-kombination-von-mehreren-arrays.html der aber nicht passt, da mehrere Arrays und nur komplette Werte vorkommen.

Gibt es da Erfahrungen oder vielleicht auch fertige Funktionen, mit denen ich arbeiten kann? Ich bin für jeden Tipp dankbar!

Florian

[Beat]

Ich habe ein Array, zB array1("a","b","c") oder array2("1","2","3","4")
und nun möchte ich alle einzelnen Werte kombinieren, so dass ich als Ergebnis sämtliche Kombinationsmöglichkeiten erhalte.

D.h
array1 ergibt abc, ab, ac, bc, a, b, c
array2 ergibt 1234, 123, 124, 134, 234, 12, 13, 14, 23, 24, 34, 1, 2, 3, 4

Keine Ahnung wie das in PHP geht.

Hier ein kleiner Perl Ansatz.

my $a=( 1 .. 10 ); #Basismaterial
my %comb=( _ => 1);

foreach my $e (@a){
  foreach my $c (keys %comb){
    $comb{ $c . $e }=1;
    $comb{ $c }=1;
  }
}
delete $comb{_};

jetzt muss man nur noch von allen Keys den _ am Anfang entfernen.

mfg Beat

[Beat]

my $a=( 1 .. 10 ); #Basismaterial
my %comb=( _ => 1);

foreach my $e (@a){
  foreach my $c (keys %comb){
    $comb{ $c . $e }=1;
    $comb{ $c }=1;
  }
}
delete $comb{_};

jetzt muss man nur noch von allen Keys den _ am Anfang entfernen.

Plözinn, einfacher

my $a=( 1 .. 10 ); #Basismaterial
my %comb=();
foreach my $e (@a){
  foreach my $c (keys %comb){
    $comb{ $c . $e }=1;
  }
  $comb{ $e }=1;
}

mfg Beat

[Dieter Raber]

Hallo Florian,

wenn ich dich recht verstehe, willst du das:

<?php  
$array1 = array("a","b","c");  
$array2 = array("1","2","3","4");  
$result_arr = array();  
foreach($array1 as $val1) {  
  foreach($array2 as $val2) {  
    $result_arr[] = $val1 . $val2;  
    $result_arr[] = $val2 . $val1;  
  }  
}  
  
print_r($result_arr);  
?>

Erklaerungen jeglicher Art ueberlasse ich den weiteren Postern.

Gruss

Dieter

[bleicher]

Grüße,
der will ja permutation innerhalb des arrays, mit n=length(array)
und ohne reihenfolge nehme ich an - wegen wiederholungen
also wäre einfach nur ich würde empfehlen einfach nur alle möglichen werte durchzugehenm, und dabei die in ein array zwischenspeichern, drauf sort() anwenden um reiohenfolge auszuschließen und dann als key benutzen um widerholungen zu vermeiden - danach noch key/werte vertauschen und du hast es.
MFG
bleicher

[Bademeister]

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

[Florian]

Hi Bademeister,

dank dir für deine schlauen Worte - ich habe deine Erklärung nun schon 8 mal gelesen und trotzdem nur einen Teil verstanden. Besonders an deinem "Trick" scheitert es leider.

So wie ich deinen Teil verstanden habe, bekomme ich nur alle Kombinationen mit allen anderen Elementen.

Mein Plan:
array("1","2","3","4") ergibt 1234, 123, 124, 134, 234, 12, 13, 14, 23, 24, 34, 1, 2, 3, 4

Bisheriger Versuch führt leider zu nem Error ;-) Ich werde aber auf jeden Fall ein bisschen weiterbasteln. Dank dir für deine Hilfe!

  
  
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: 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 jedes Element einer der Kopien $lastElement  
       dranklatschen. Dann die beiden Array zusammenfügen und zurückgeben.  
    */  
        $array1 = $subPowerSet;  
        $array2 = array_map($lastELement, $subPowerSet);  
  
        print_r(array_merge_recursive($array1, $array2));  
  
  
}  
  

[Bademeister]

Besonders an deinem "Trick" scheitert es leider.

Ist gar nicht meiner - den hab ich abgeguckt :-)

So wie ich deinen Teil verstanden habe, bekomme ich nur alle Kombinationen mit allen anderen Elementen.

Mein Plan:
array("1","2","3","4") ergibt 1234, 123, 124, 134, 234, 12, 13, 14, 23, 24, 34, 1, 2, 3, 4

Also: Wenn man (erstmal) zu den obigen Teilmengen der Menge {1,2,3,4} noch die leere Menge dazutut, dann hat man 16 Stück. Klar - zu jedem Element kann man entweder 'ja, kommt rein', oder 'nein, bleibt draußen' sagen, das macht 2^4 Mögliche Teilmengen. Nun enthalten genau acht davon die 1, und 8 enthalten sie nicht.

Wenn ich mir die 8 angucke, die die 1 nicht enthalten, dann ist das gerade die Potenzmenge der Menge {2,3,4}. Klar - die Menge aller Teilmengen von {1,2,3,4}, die die 1 nicht enthalten, ist gerade die Menge aller Teilmengen von {2,3,4}.

Und die anderen acht sind gerade - genau - wieder dieselben acht wie vorher, mit noch ner 1 dazu. Das ist die Idee der Rekursion.

$array1 = $subPowerSet;
        $array2 = array_map($lastELement, $subPowerSet);

Schau Dir bitte nochmal array_map im Handbuch an. Ganz so einfach kriegste die Rosinen hier nicht :-)

print_r(array_merge_recursive($array1, $array2));

Warum 'recursive'?

Viele Grüße,
der Bademeister

[Florian]

Alles klar, ich bastel noch mal ein bisschen. Danke auf jeden Fall für deine Hilfe und die Rosinen werde ich schon finden ;)

[Florian]

Ich komme nicht weiter, da ich die String-Variable nicht übergeben kann.

  
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: 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 jedes Element einer der Kopien $lastElement  
       dranklatschen. Dann die beiden Array zusammenfügen und zurückgeben.  
    */  
       $array1 = $array;  
       $array2 = array_map("add", $array);  
  
       return array_merge($array1, $array2);  
  
}  
  
function add($array){  
      return array_push($array, $lastElement);  
}  

Klingt so einfach, aber daran scheitert es leider! Einen kleinen Hinweis bitte noch, Bademeister ;) Oder hab ich den Trick falsch verstanden??

Danke!

[Bademeister]

Ich komme nicht weiter, da ich die String-Variable nicht übergeben kann.
[...]

function add($array){
      return array_push($array, $lastElement);
}
[/code]

Du hast mehrere Moeglichkeiten:

1.: Benutze array_walk statt array_map, dann kannst Du den Wert an die Funktion uebergeben. Ab PHP 5.3 kannst Du 'add' auch als anonyme Funktion implementieren und mit Parametern fuettern.

2.: Implementiere das Array als Objekt (entweder haendisch oder als Erweiterung der Klasse ArrayObject), und gib der Klasse die Methode PowerSet. Deine Callbackfunktion 'add' kann dann als (geschuetzte) Methode der Klasse implementiert werden und hat dann Zugriff auf den Wert von $lastElement, wenn dieser als Eigenschaft des Objektes (und nicht nur als lokale Variable in der Funktion PowerSet) gespeichert wird. Weiss nicht, ob das jetzt eher fortgeschritten fuer Dich klingt(?), aber das waere jedenfalls meine Empfehlung.

Oder hab ich den Trick falsch verstanden??

Nein, gar nicht. Sieht insgesamt gut aus.

Viele Gruesse,
der Bademeister

[Florian]

Klasse Sache - tiptop! Sehr simple Erklärung - damit komme ich sicher wieder ein Stück weiter. Ich lasse dich wissen, wenn ich fertig bin (oder noch weitere Probleme auftauchen).

Lass uns doch via Xing vernetzen - vielleicht kann ich mich in Zukunft mal für deine Hilfe revanchieren.

Florian