Alle String-Variationen aus Array auflisten

D

DaRealMC

Erfahrenes Mitglied
Hallo zusammen,

mit Sicherheit gibt es dieses Problem schon, allerdings wüsste ich nciht mal, wie ich danach suchen soll :(
Mein Problem:
Ich habe ein Array
PHP: 
$arr=array('','A','C','Z');
und benötige am Ende eine Liste mit allen damit möglichen Kombinationen und das ganze bis zu einer Länge von 10(!)
Dabei muss jede Zeile einzeln ausgegeben werden
PHP: 
echo($string."\r\n");

Am Ende soll das ganze so aussehen:
Code: 
A
C
Z
AA
AC
AZ
CA
CC
CZ
ZA
ZC
ZZ
AAA
AAC
[...]
ZZZZZZZZZZ

Vermutlich funktioniert das "am einfachsten" über Iteration mit foreach, aber ich komm einfach auf keinen grünen Zweig :(
(Und ja, ich weiß, dass das am Ende eine Ausgabe von 1048576 Zeilen wird.)


//Update:
Habe mittlerweile das gefunden:
http://r.je/php-find-every-combination.html
PHP: 
$words = array('red', 'blue', 'green');   
$num = count($words); 

//The total number of possible combinations 
$total = pow(2, $num);

//Loop through each possible combination  
for ($i = 0; $i < $total; $i++) {  
    //For each combination check if each bit is set 
    for ($j = 0; $j < $num; $j++) { 
       //Is bit $j set in $i? 
        if (pow(2, $j) & $i) echo $words[$j] . ' ';      
    } 
    echo '<br />'; 
}
Leider fehlen dabei aber die Kombinationen wie red red oder green red
 
Zuletzt bearbeitet:
PHP: 
<?php

// Ziehe viermal mit Zurücklegen aus [a, b, c, d]
$elements = array('a', 'b', 'c', 'd');
$draw = 4;

// Anzahl Elemente
$elements_count = count($elements);

// Anzahl möglicher Resultate
$n = pow($elements_count, $draw);

// Jedes Resultat ermitteln...
for ($i = 0; $i < $n; $i++) {
    $tmp = str_pad(base_convert($i, 10, $elements_count), $draw, '0', STR_PAD_LEFT);
    $tmp2 = str_replace(array_keys($elements), $elements, $tmp);

    echo $tmp2 . "\n";
}

Aus diesem Thread:

- http://www.php.de/php-einsteiger/104670-php-kombinationsmoeglichkeiten.html

Code: 
aaaa
aaab
aaac
aaad
aaba
aabb
aabc
aabd
aaca
aacb
aacc
aacd
aada
aadb
aadc
aadd
abaa
...
dccb
dccc
dccd
dcda
dcdb
dcdc
dcdd
ddaa
ddab
ddac
ddad
ddba
ddbb
ddbc
ddbd
ddca
ddcb
ddcc
ddcd
ddda
dddb
dddc
dddd

Ist vielleicht etwas hacky. :)

Hier noch für $draw=2:

Code: 
aa
ab
ac
ad
ba
bb
bc
bd
ca
cb
cc
cd
da
db
dc
dd

Wenn du das so willst, kannst du noch einmal eine Schleife drumrum machen, in der du $draw von 1 bis 10 hochzählst.
 
Ich habe es noch mal „händisch“ gemacht:

PHP: 
<?php

// Ziehe dreißigmal mit Zurücklegen aus [a, b, c]
$elements = array('a', 'b', 'c');
$draw = 30;

// Anzahl Elemente
$elements_count = count($elements);

// Anzahl möglicher Resultate
$n = pow($elements_count, $draw);

// Die letzten sechs Resultate ermitteln
for ($i = $n - 6; $i < $n; $i++) {
    echo $i . ': ';

    $x = $i;
    for ($exp = $draw - 1; $exp >= 0; $exp--) {
        $a = (int) floor($x / pow($elements_count, $exp));

        echo $elements[$a];

        $x -= $a * pow($elements_count, $exp);
    }

    echo "\n";
}

// 205891132094643: ccccccccccccccccccccccccccccba
// 205891132094644: ccccccccccccccccccccccccccccbb
// 205891132094645: ccccccccccccccccccccccccccccbc
// 205891132094646: ccccccccccccccccccccccccccccca
// 205891132094647: cccccccccccccccccccccccccccccb
// 205891132094648: cccccccccccccccccccccccccccccc

Auch das ist aber limitiert durch die Größe der Datentypen. Das Beispiel wird nicht mit einem 32-bit-PHP korrekt laufen.

Für größere Bereiche müsste man es etwa per bcmath implementieren.

- http://de3.php.net/manual/en/book.bc.php

(Ich weiß nicht, ob das für eine Beispiellösung sinnvoll ist.)

Du solltest beim geposteten Code in jedem Fall für deinen Anwendungsfall prüfen, ob zumindest die letzte Permutation stimmt. Irgendwann läuft die Sache in Limits.

PS: Hier wird möglicherweise in Zukunft die „beste“ Variante zu finden sein: http://php-de.github.io/jumpto/kombinatorik-loesungen/ Gerade für spätere Leser könnte sich der Klick lohnen.
 
Zuletzt bearbeitet:
Hallo,

m.E. ist es einfacher, wenn man sich für alle Kombinationen ein Array zusammensetzt und das über die implode-Funktion als String ausgibt:
PHP: 
$arr = array('', 'A', 'C', 'Z');
$strLength = 10;

    /* Leere Elemente im extension-Array entfernen: */
    $arrExt = array_values(array_filter($arr));

    /* current-Array und result-Array initialisieren: */
    $arrCurr = $arrResult = $arrExt;

    function extItems($arrCurr, $arrExt)
    {
        /* Rückgabearray initialisieren: */
        $arrRes = array();
        /* Jedes Element vom $arrCurr mit jedem Element des $arrExt kombinieren: */
        foreach($arrCurr as $currItem)
            foreach($arrExt as $extItem)
                $arrRes[] = $currItem.$extItem;
        return $arrRes;
    }

    do {
        $arrCurr = extItems($arrCurr, $arrExt);
        /* Ergebnis komplettieren: */
        $arrResult = array_merge($arrResult, $arrCurr);
    } while(strlen($arrCurr[count($arrCurr) - 1]) < $strLength);

// Ausgabe:
//echo '<pre>', print_r($arrResult), '</pre>';
echo '<pre>', implode("\r\n", $arrResult), '</pre>';
Läuft bei mir problemlos auf 32-Bit.
 
Das skaliert nicht. Da du alles gleichzeitig im Speicher hast, verbrauchst du in dem Skript pro ~3.000 Einträge schon 1 MB RAM (überschlagen nach Ausgabe von memory_get_peak_usage()). Dein Beispiel mit ~90.000 Einträgen steht schon bei 30 MB. Damit kommst du nicht mal in die Größenordnung von 2 Mrd., ab der die 32-bit-Architektur zum Problem wird. Du würdest schon lange vorher Terabytes an Speicher benötigen.
 
Wenn du die Ausgabe rausnimmst und diese Zeilen ergänzt, kannst du es ablesen:

PHP: 
// Ausgabe:
//echo '<pre>', print_r($arrResult), '</pre>';
#echo '<pre>', implode("\r\n", $arrResult), '</pre>';

echo '$strLength = ' . $strLength . "\n";

echo 'Entries: ' . count($arrResult) . "\n";

echo 'mem_peak_usage: ' . memory_get_peak_usage() . "\n";

Code: 
$strLength = 8
Entries: 9840
mem_peak_usage: 3958168

$strLength = 9
Entries: 29523
mem_peak_usage: 11450232

$strLength = 10
Entries: 88572
mem_peak_usage: 33336448

$strLength = 11
Entries: 265719
mem_peak_usage: 102140536

$strLength = 12
Entries: 797160
mem_peak_usage: 308028424
 
Bei mir stößt das Script bei 12 Stellen ans Limit:
Code: 
/*
 * $strLength = 10
 * Entries: 88572
 * mem_peak_usage: 19127824
 *
 * $strLength = 11
 * Entries: 265719
 * mem_peak_usage: 58489432
 *
 * Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 36 bytes) in C:\xampp\htdocs\usw.usf.
 */
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück