[PHP/Algorithmus] Alle möglichen Kombinationen

J

Johnson

Code-Frevler
ID: 118054
L
20 April 2006
859
53
Hi,

ich frage mich gerade, wie ich folgendes Problem möglichst effektiv lösen könnte (das Problem ist sehr bruteforce ähnlich):

Ich habe ein Array:
PHP: 
$ar = array('a',array('b','c'),'d');

Nun möchte ich alle möglichen Kombinationen der ersten "Unterarrays" ausgeben, eben

abd
acd

Wie stelle ich das nun am Geschicktesten an ?

Ich hatte mir überlegt eine Art Code zu kreieren, also 000 und 010 (für die Nummer der numerischen Indizes), allerdings bin ich von dieser Möglichkeit weniger angetan ...

Gruß
 
Rekursiv mit foreach($string as $char_or_array) durchgehen und konkatenieren ? :think:
(nur so als Anstoß, keine Ahnung, ob sich das so einfach umsetzen lässt)
 
Neija brauchst du definitiv alle Möglichkeiten oder nur die Zahl der Möglichkeiten?
Also ich würde es auch in Schleifen lösen auf Grund des Speicherbedarfs (selbst mit Referenzen braucht rekursiv mehr Speicher)

Ps.: wie findest du eigentlich das neue PHP Magazin? Also es ist das erste Mal, dass mich kein Artikel so richtig interessiert hat.
 
Ist warscheinlich bissi umständlich aber mir fiel keine dynamische Lösung ein:

PHP: 
$x = 0;		// äußere Array values
$y = 0;		// unterarray values
foreach($ar AS $key => $val)
{
	if(is_array($val))
		foreach($val AS $key => $val)
			$y++;
	else
		$x++;
}

$v = 0;
for($a=0; $a < $y; $a++)
{
	$br[] = $ar[0].$ar[1][$v].$ar[2];
	$v++;
}
echo "<pre>";print_r($br);echo "</pre>";

geht mit deinem Array und mit solch einem:
PHP: 
$ar = array('a',array('b','c','h','n'),'d');
wichtig ist das der Unterarray sich dynamisch erweitern kann aber wenn es im Array selber mehr Elemente werden, musst du die zeile
PHP: 
$br[] = ...
halt dementsprechend anpassen.
*edit
das $x++; kannst durch continue; ersetzten wird ja im endeffekt nicht gebraucht
 
Zuletzt bearbeitet:
Hi,

danke für die Antworten :)

Erstmal: Ja, ich brauche alle Möglichkeiten und nicht nur die Anzahl.

@theHacker: Hmm, wie meinst du das genau ?

@ice-breaker: Das einzig wirklich interessante finde ich das mit der muli-Sprachumsetzung. Ansonsten habe ich auch schonmal mehr Artikel gelesen ;)

@strolch00: Aufgrund der fehlenden Dynamik leider nicht das was ich brauche :(

Da muss es doch irgendeine schönere Lösung geben ...

Gruß
 
Johnson schrieb:
@theHacker: Hmm, wie meinst du das genau ?
Zum Vergrößern anklicken....
Ich hatte es mir so in der Art vorgestellt:
PHP: 
/* nicht unbedingt echter PHP-Code ^^ */

function get_all_words($arr,$pre="",$post="")
// $pre und $post nehmen bei Rekursion die Teile, um das "Array-Zeichen" mit
{
  $res=array();
  $string="";

  foreach($arr as $char_or_array)
  {
    if(!is_array($char_or_array())
      $string.=$char_or_array;
    else
      array_merge_oder_wie_das_heisst($res,get_all_words($char_or_array,$string,$die_zeichen_die_noch_kommen_wuerden));
  }
  $res[]=$pre.$string.$post;
  return $res;
}

$arr=array('a',array('b',array('c','d')),'e');
print_r(get_all_words($arr));
Hab aber festgestellt, dass es, wie ich angenommen hatte, doch nicht so einfach is :biggrin:
 
Johnson schrieb:
*verwirrt bin*
Zum Vergrößern anklicken....
Ich versteh deinen Post auch nicht wirklich :mrgreen:
Johnson schrieb:
Allerdings glaube ich, dass $char_of_array kein Array sein könnte, allerdings $arr ein Unterarray ist.
Zum Vergrößern anklicken....
Ich hab das Ding $char_or_array bezeichnet ;)
Vielleicht hast du deshalb ja n Denkfehler drin, oder kp :biggrin:

In $char_or_array ist entweder ein String, also ein einzelner Buchstabe, oder ein Array. Wenn es ein Zeichen is, wird das einfach konkatentiert. Für den Fall, dass es ein Array ist, müssen alle Möglichkeiten durchgespielt werden.

Optimal würde
PHP: 
$arr=array('a',array('b','c'),array('d','e'));
so durchlaufen:
PHP: 
// Initialaufruf
// ""
get_all_words(array('a',array('b','c'),array('d','e')));
// "A"
A.get_all_words(array('b','c')),get_all_words(array('d','e'));
// "AB".get_all_words(array('d','e')
A.B.get_all_words(array('d','e'));
// "ABD"
// "ABE"
// "AC".get_all_words(array('d','e')
A.C.get_all_words(array('d','e'));
// "ACD"
// "ACE"
Ergebnisse: ABD, ABE, ACD, ACE

Ich hatte es nur noch ned raus, wie ich den Rest (in meinem Versuch $pre und $post) übergebe, da das ja wieder Arrays (sogar mit vielen, vielen Unterarrays) sein könnten.
 
Es geht auch ohne Rekursion. Gibt aber momentan von mir nur den Code, für grossartige Erklärungen habe ich noch 'nen zu grossen Hangover. :sing:
PHP: 
<?php
  $ar = array('a',array('b','d'),'c');
  
  $result = Array('');
  foreach ($ar as $item) {
    if (!is_array($item)) {
      $item = Array($item);
    }

    $turn_result = Array();
    foreach ($result as $resultitem) {
      foreach ($item as $itemitem) {
        array_push($turn_result, $resultitem.$itemitem);
      }
    }
    $result = $turn_result;
  }
  
  print_r($result);
?>
 
@tleilax:
Wenn ich deinen Code richtig verstanden hab, würde er bei einem Array mit Tiefe 3 versagen ? :think:

$ar = array('a',array('b',array('e','f'),'d'),'c');
müsste dann u.a. auch aArrayc liefern :think:

Werd ich später mal ausprobiern, ob ich richtig kombiniert hab :biggrin:
 
Nene, musste gar nicht erst ausprobieren. Das stimmt schon, dass es bei 3-dimensionalen Arrays nicht funktionieren würde. Aber ich hatte dann wohl die Anforderung falsch verstanden. Dachte, es gibt maximal ein 2-dimensionales Array.
 
tleilax schrieb:
Es geht auch ohne Rekursion. Gibt aber momentan von mir nur den Code, für grossartige Erklärungen habe ich noch 'nen zu grossen Hangover. :sing:
Zum Vergrößern anklicken....

Funktioniert, dankeschön!

Die Funktionsweise hat sich mir nun nach mehrmaligem Probeausgeben usw auch geöffnet - prinzipiell kann man da ja auch selber draufkommen :ugly:

edit: Ja, es geht auch hier nur um 2-dimensionale Arrays :)

theHacker schrieb:
@tleilax:
Wenn ich deinen Code richtig verstanden hab, würde er bei einem Array mit Tiefe 3 versagen ? :think:
Zum Vergrößern anklicken....

Schöne Diskussion, deine These stimmt, meinem Problem ist es aber egal :p
 
theHacker schrieb:
Ich hatte es nur noch ned raus, wie ich den Rest (in meinem Versuch $pre und $post) übergebe, da das ja wieder Arrays (sogar mit vielen, vielen Unterarrays) sein könnten.
Zum Vergrößern anklicken....

rekursiv ginge es z.b. so zu lösen:

PHP: 
function get_all_words( $arr, $res=array() )
{
  if( count($res)==0 ) $res = array(''); // erster aufruf
  foreach( $arr as $c_a ) 
  {
    $tmp  = array(); // neue ergebnisse speichern
    if( is_string($c_a) ) $c_a = array( $c_a ); // string -> array
    foreach( $c_a as $c )
      if( is_string($c) ) // bei string concat mit allen elementen
        foreach( $res as $a ) $tmp[] = $a.$c;
      else // sonst rekursiv
        $tmp = get_all_words( $c_a, $res );
    $res  = $tmp; // alte ergebnisse überschreiben
  }
  return $res;
}

$test = array( "a", array( "b", array( "c", "d" ) ), array( "e", "f", "g" ), "h" );
var_export( get_all_words( $test ) );

habs aber jetzt nicht bis in die ewigkeit getestet :(
 
@ActionScripter:
Mir scheint, ich hab das Problem missverstanden.

Dein Code liefert für
PHP: 
$test = array( "a", array( "b", array( "c", "d" ) ), array( "e", "f", "g" ), "h" );
dieses Ergebnisarray:
Code: 
Array (     [0] => abceh     [1] => abdeh     [2] => abcfh     [3] => abdfh     [4] => abcgh     [5] => abdgh )
Ich dachte, das sollte rauskommen:
abeh, abfh, abgh, aceh, adeh, acfh, adfh, acgh, adgh
Zum Vergrößern anklicken....
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben