Berechnung möglicher Lösungen in einem PHP Array: Wie kann ich meinen Algorithmus verbessern?

Question

Präambel:

Diese Frage nicht über PHP zu lernen, noch ist es Code, ich plane, in einer produktiven Umgebung zu verwenden. Ich will nur so sehen und lernen, wie ich diese Art von Arbeit erledigen kann. Bitte korrigieren Sie also nur meinen Code oder zeigen Sie mir bessere, schnellere oder kürzere Lösungen dafür. Das Problem selbst wurde bereits gelöst. Vielen Dank!

---

Das Problem:

Vor einigen Tagen ein Benutzer asked a question hier auf SO. Sein Problem hat meine Aufmerksamkeit bekommen, denn ich wollte einen Weg finden, seine Bedürfnisse zu lösen.

Er wollte alle möglichen Schlüssel Kombinationen eines PHP array, wo die Summe des Wertes100 oder so nah wie möglich auf 100. Er hatte uns ein Beispiel Array gegeben, die ich auch für meine Beispiele verwenden:

$array = array(25, 30, 50, 15, 20, 30); 

Zum Beispiel ein Ergebnis [2, 4, 5] sein sollte, weil 50 + 20 + 30100 ist.

$sum = $array[2] + $array[4] + $array[5]; // = 100 

Ich denke, die Grundidee sollte klar sein. Lassen Sie uns jetzt einen Blick auf meine Arbeit nehmen ...

---

Mein Ansatz:

Also dieses Problem meine Aufmerksamkeit als Entwickler erhalten hat. Zuerst dachte ich, es wäre ziemlich einfach. Tun Sie einfach etwas Ergänzung und überprüfen Sie das Ergebnis. Aber dann habe ich bemerkt, dass da einige Punkte zu beachten sind ...

Es gibt viele Kombinationen zu testen. Für das Beispiel-Array gäbe es bis zu 720() mögliche Permutationen. Um alle möglichen Kombinationen zu erhalten, wollte ich zuerst alle möglichen Permutationen des Arrays bekommen.

Aber das war nur die halbe Wahrheit. Da es im Array doppelte Werte geben könnte (wie in Ihrem Beispiel 30), konnten wir nicht alle möglichen Permutationen der Array-Werte erhalten, stattdessen mussten wir alle möglichen Permutationen der Array-Schlüssel erhalten.

Also ich habe die pc_permut Funktion der php cookbook verwendet und für meine Bedürfnisse geändert. Es wird alle möglichen Permutationen in einem Array von Schlüsseln zurückgeben.

/** 
* gets all possible permutations of $array 
* @param array $array 
* @param array $permutations 
* @return array 
*/ 
function permutations($array, $permutations = array()) { 
    if(!empty($array)) { 
     $result = array(); 

     for($i = count($array) - 1; $i >= 0; --$i) { 
      $newItems = $array; 
      $newPerms = $permutations; 
      list($values) = array_splice($newItems, $i, 1); 
      array_unshift($newPerms, $values); 
      $result = array_merge($result, permutations($newItems, $newPerms)); 
     } 
    } 
    else { 
     $result = array($permutations); 
    } 

    return $result; 
} 

Das Ergebnis dieser Funktion ist ein mehrdimensionales Array, das alle Permutationen in einem geordneten Schlüssel-Array enthält.

Array (
    [0] => Array (
     [0] => 0 
     [1] => 1 
     [2] => 2 
     [3] => 3 
     [4] => 4 
     [5] => 5 
    ) 
    [1] => Array (
     [0] => 1 
     [1] => 0 
     [2] => 2 
     [3] => 3 
     [4] => 4 
     [5] => 5 
    ) 
    [... 
) 

Also, für jetzt habe ich alle Permutationen mit zu arbeiten. Die Berechnung der möglichen Kombinationen ist gar nicht so schwer.Ich werde einfach die Permutation durchlaufen, die Summe erhöhen, bis sie 100 oder höher erreicht haben und die Tastenkombination zurückgeben.

Aber ich finde heraus, dass ich eine Sache verpasst habe. Da ich alle möglichen Permutationen erhalten habe, sind sogar einige Ergebnisse in der Liste doppelt vorhanden. Um zu erklären, diese beiden Ergebnisse sind im Grunde das gleiche:

[2, 4, 5]; // 50 + 20 + 30 = 100 
[4, 5, 2]; // 20 + 30 + 50 = 100 

Ich habe das Sortieren nach der Berechnung die Schlüssel endete und sie als Index in der resultierenden Array. Es wäre also sicher, dass jede Kombination nur einmal im Ergebnis existiert. Das ist meine combinations Funktion:

/** 
* gets all possible key combinations of $array with a sum below or equal $maxSum 
* @param array $array 
* @param integer $maxSum 
* @return array 
*/ 
function combinations($array, $maxSum) { 
    // get all permutations of the array keys 
    $permutations = permutations(array_keys($array)); 
    $combinations = array(); 

    // loop all permutations 
    foreach($permutations as $keys) { 
     // create a container for each permutation to store calculation 
     $current = array(
      "sum" => 0, 
      "keys" => array() 
     ); 

     // now loop through the permutation keys 
     foreach($keys as $key) { 
      // if the addition is still between or equal $maxSum 
      if($current["sum"] + $array[$key] <= $maxSum) { 
       // increment the sum and add key to result 
       $current["sum"] += $array[$key]; 
       $current["keys"][] = $key; 
      } 
     } 

     // to be sure each combination only exists once in the result 
     // order the keys and use them as array index 
     sort($current["keys"]); 
     $combinations[join("", $current["keys"])] = $current; 
    } 

    // remove the created key-index from array when finished 
    return array_values($combinations); 
} 

Die Ausführung nach vorne einfach gerade ist:

$array = array(25, 30, 50, 15, 20, 30); 
print_r(combinations($array, 100)); 

Das Ergebnis ist ein Array, alle Kombinationen enthalten. Für unser Beispiel-Array gibt es elf mögliche Kombinationen. Das Ergebnis sieht wie folgt aus:

Array (
    [0] => Array (
     [sum] => 90 
     [keys] => Array (
      [0] => 0 
      [1] => 1 
      [2] => 3 
      [3] => 4 
     ) 
    ) 
    [1] => Array (
     [sum] => 90 
     [keys] => Array (
      [0] => 0 
      [1] => 2 
      [2] => 3 
     ) 
    ) 
    [... 

Da ich dieses Skript als answer of the original question geschrieben habe, werde ich mich fragen, ob es eine andere sein würde, noch besser, die Arbeit zu tun. Vielleicht gibt es einen Weg ohne Permutationen oder eine Möglichkeit, gleiche Kombinationen aus der Berechnung oder dem resultierenden Array auszuschließen. Ich weiß, dass ich die Berechnung auch direkt in der permutations Funktion ausführen könnte, aber das wäre im Grunde der gleiche Arbeitsablauf.

Ich würde wirklich gerne einige Ratschläge, Tipps oder Verbesserungen von Ihnen bekommen. Ich denke, hier ist etwas Potenzial, um das Skript zu verbessern, aber ich habe eigentlich keine Ahnung, wie. Aber ich bin mir sicher, es könnte einfacher und einfacher gemacht werden ...

Danke für Ihre Zeit! :)

Answer 1

das Array Sortierung führt zu einigen Möglichkeiten: hier ist die, die ich von denke:

bezeichne ich eine (selectedIndexes) das Element besteht aus allen Elementen von selectedIndexes z.B. a ({25, 30, 30}) = (25, 30, 30)

P (n) ist die Menge aller Kombinationen der Indizes 1 bis n und aus Gründen der Übersichtlichkeit beginnt meine Arrays bei Index 1 (Also P (2) = {1, 2, (1, 2)})

Ich verwende 2 Break-Bedingungen im Pseudocode unten erklärt. 1. ist das erste Element von aSort = die erlaubte Summe. zweite ist die Summe zu klein ist im Vergleich zu Asorted erste Element

selectedIndexes = {} 
    sum = 100 
    aSorted = {15, 20, 25, 30, 30, 50} //starting values for the example 
             //to clarify the following function 
    aSum = {15, 35, 60, 90} 

function n(aSorted, sum, selectedIndexes){ 
    compute aSum //precisely search in aSum for the index at which 
       //the elements are bigger than sum, and cut 
    answer = (P(count(aSum))) X a(selectedIndexes) // with X being the cartesian product 

    for (i=count(aSum)+1; i<=count(aSorted); i++){ 
     newASorted = splice(aSorted, count(aSum)) 
     // 1st break condition 
     if(newASorted is empty) return answer 
     // 2nd break condition the new sum < the first element of aSorted 
     if (aSorted(i)<sum && sum-aSorted(i)>=aSorted(1)){ 
      answer += n(newASorted, sum-aSorted(i), push(selectedIndexes,  
      i)) 
     } 
    } 
return answer 
} 

Die Komplexität dieses Algorithmus quadratischen fühlt sich (nach einem kurzen Check, es ist mehr wie der Ordnung n^log 2 (n)) in Bezug auf die Anzahl von Elementen in dem Array

Um es weniger abstrakt, lassen sie sich das Beispiel entwickelt (Warnung vertrauen, dass ich das Beispiel mehr als der Pseudo-Code, obwohl ich Ungenauigkeiten mich nicht sehen, in dem Pseudo-Code): 15

n ({ , 20, 25, 30, 30, 50}, 100, {}) = P (4) + n ({15, 20, 25, 30, 30}, 50, {6}) + n ({15, 20 , 25, 30}, 70, {5})

Ausgehend von der ersten n in Abhängigkeit von der rechten Seite der Gleichung der Entwicklung

n ({15, 20, 25, 30, 30}, 50, {5}) = (P (2) X { 6}) + n ({15, 20, 25, 30}, 20, {5, 6}) + n ({15, 20, 25}, 20, {4, 6}) + n ({15, 20 }, 25, {3, 6})

n ({15, 20, 25, 30}, 20, {5, 6}) = (P (1) X {(5, 6)})// + n ({15}, 0, {2, 5, 6}) (aber 0 < 15) Bruchbedingung 2

n ({15, 20, 25}, 20, {4, 6}) = P (1) X {(4, 6)} // und Bruchbedingung 2

n ({15, 20}, 25, {3, 6}) = P (1) X {(3, 6)} // + n ({15}, 5, {2, 3, 6}) (aber 5 < 15) Unterbrechungsbedingungs 2

nun die zweiten n in Abhängigkeit von der rechten Seite der Gleichung der Entwicklung

n ({15, 20, 25, 30}, 70, {5}) = (P (3) X {5}) + n ({15, 20, 25}, 40, {4, 5})

n ({15, 20, 25}, 40, {4, 5}) = (P (2) X {(4, 5)}) + n ({15, 20}, 15, {3, 4, 5})

n ({15, 20}, 15, {3, 4, 5}) = P (1) x {(3, 4, 5)} // + n ({}, 0, {1, 3, 4, 5}) neue Abbruchbedingung aSum ist leer