https://www.php-rocks.de/mitglieder/2-arne-drews.html
Registriert seit: 18.03.2015 | Themen: 59 | Beiträge: 364
Bewertung:
14
PHP Selbsteinschätzung: Fortgeschrittene Kenntnisse
Hallo,
Ich habe mal Anforderung, die eher auf mathematischer Logik basiert.
Es gibt eine Menge an Einzelwerten, aus denen ich eine Summe herausfinden muß.
Beispiel:
Ausgabe: Einzelwerte:
46.93
78.44
9.01
46.93
334.37
19.90
usw.
Jetzt habe ich eine Summe von bspw. 515.68 und muß herausfinden, aus welchen Werten der Liste sich diese zusammensetzen "könnte".
In diesem Fall war es "zu Fuß" noch relativ einfach ( 334.37 + 9.01 + 46.93 + 46.93 + 78.44 ), aber ich habe weitere solcher Fälle, bei denen ich das nicht so leicht hinbekomme.
Auf welcher mathematischen Logik basierend kann ich das in PHP umsetzen?
Danke
https://www.php-rocks.de/mitglieder/16-mermshaus.html
Registriert seit: 20.03.2015 | Themen: 3 | Beiträge: 50
Bewertung:
6
PHP Selbsteinschätzung: Fortgeschrittene Kenntnisse
08.06.2016, 23:07
Dieser Beitrag wurde zuletzt bearbeitet: 09.06.2016, 00:59 von mermshaus.
Bearbeitungsgrund: Eine $verbose-Bedingung fehlte
Geht in den Bereich der Kombinatorik. Backtracking wäre wohl ein sinnvoller Ansatz.
- https://de.wikipedia.org/wiki/Backtracking
Um wie viele Werte handelt es sich denn?
Hier eine zusammengeschusterte Brute-Force-Lösung, die den Algorithmus für „Ziehen ohne Zurücklegen“ nutzt (z. B. Lotto, 6 aus 49), den ich vor Jahren mal gebastelt habe:
(Das ist keine Backtracking-Variante.)
(Edit: Und wo ich schon Lotto erwähne: Alle Angaben sind wie immer ohne Gewähr.)
PHP-Code:
<?php
// Code bis Trennstrich (=======) 1:1 von hier kopiert: // http://php-de.github.io/jumpto/kombinatorik-loesungen/#alle-kombinationen-einer-bestimmten-anzahl-der-elemente-eines-arrays
/** * Calculates the factorial of a given non-negative integer * * @param int $n Non-negative integer * @return int Factorial of $n */ function fac($n) { if (!is_int($n) || $n < 0) { throw new InvalidArgumentException( 'n has to be a non-negative (int)'); }
for ($f = 1; $n > 1; $n--) { $f *= $n; }
return $f; }
function nChooseK($n, $k) { $top = 1; $bottom = 1;
for ($i = 0; $i < $k; $i++) { $top *= $n - $i; $bottom *= $i + 1; }
return $top / $bottom; }
/** * Creates a lookup table for Fibonacci numbers * * Table size: (N - k + 1) * k * * @param $n int N * @param $k int k * @return array Lookup table for this (N choose k) */ function calcLookupTable($n, $k) { $b = $n - $k + 1; $fib = range(0, $k - 1);
for ($i = 0; $i < count($fib); $i++) { $fib[$i] = range(0, $b - 1); $fib[$i][0] = 1; }
for ($x = 0; $x < $k; $x++) { for ($y = 1; $y < $b; $y++) { $p = (isset($fib[$x - 1][$y])) ? $fib[$x - 1][$y] : 0; $q = (isset($fib[$x][$y - 1])) ? $fib[$x][$y - 1] : 0; $fib[$x][$y] = $p + $q; } }
return $fib; }
/** * Returns path vector by number * * @param $n int N * @param $k int k * @param $w int Path number (between 1 and (N choose k)) * @param $fib array Lookup table for (N choose k) (see calcLookupTable) * @return array Path at given index */ function getPathByNumber($n, $k, $w, array $fib) { $b = $n - $k + 1; $x = range(0, $k - 1);
for ($i = 0; $i < $k; $i++) { $j = 1; $u = $fib[$k - $i - 1][$b - $j]; while ($u < $w) { $j++; $u += $fib[$k - $i - 1][$b - $j]; } $x[$i] = ($i > 0) ? $x[$i - 1] + $j : $j; $w = $w - ($u - $fib[$k - $i - 1][$b - $j]); $b = $b - $j + 1; }
return $x; }
// ============================================================================= Ab hier neu
function findShortestSolution($numbers, $sumToFind, $verbose = true) { $numberCount = count($numbers);
$tries = 1;
for ($k = 1; $k <= $numberCount; $k++) {
$w = nChooseK($numberCount, $k);
if (true === $verbose) { echo '[' . date('Y-m-d H:i:s') . '] Running... k = ' . $k . ' (' . $w . " iterations)\n"; }
$fibTable = calcLookupTable($numberCount, $k);
for ($draw = 1; $draw <= $w; $draw++) { $path = getPathByNumber($numberCount, $k, $draw, $fibTable);
$sumx = 0;
foreach ($path as $element) { $sumx += $numbers[$element - 1]; }
if ($sumToFind === $sumx) { $solution = array(); foreach ($path as $element) { $solution[] = $numbers[$element - 1]; }
if (true === $verbose) { echo '[' . date('Y-m-d H:i:s') . '] Found solution in ' . $tries . " tries\n"; }
return $solution; }
$tries++; } }
return array(); }
// Zum Test: Bilde 20 Zufallszahlen. Wähle daraus zufällig 10 Elemente. Bilde // die Summe dieser Elemente. Versuche anhand der Summe und der 20 Zufallszahlen // die 10 Elemente zu finden.
$numberCount = 20; $elementsInSum = 10;
for ($i = 0; $i < $numberCount; $i++) { $numbers[] = rand(0, 10000); }
sort($numbers);
$tmp = $numbers; shuffle($tmp);
$sumToFind = array_sum(array_slice($tmp, 0, $elementsInSum));
$solution = findShortestSolution($numbers, $sumToFind);
echo 'Numbers: ' . implode(', ', $numbers) . "\n"; echo 'Sum to find: ' . $sumToFind . "\n"; echo 'Shortest solution: ' . $sumToFind . ' = ' . implode(' + ', $solution) . "\n";
Code:
[2016-06-08 22:04:49] Running... k = 1 (20 iterations)
[2016-06-08 22:04:49] Running... k = 2 (190 iterations)
[2016-06-08 22:04:49] Running... k = 3 (1140 iterations)
[2016-06-08 22:04:49] Running... k = 4 (4845 iterations)
[2016-06-08 22:04:49] Running... k = 5 (15504 iterations)
[2016-06-08 22:04:49] Running... k = 6 (38760 iterations)
[2016-06-08 22:04:50] Running... k = 7 (77520 iterations)
[2016-06-08 22:04:50] Found solution in 68762 tries
Numbers: 96, 470, 592, 1127, 1325, 1387, 1776, 3752, 4611, 5860, 5923, 6193, 6199, 6684, 7517, 7518, 9581, 9723, 9869, 9878
Sum to find: 40911
Shortest solution: 40911 = 96 + 470 + 5860 + 7517 + 7518 + 9581 + 9869
https://www.php-rocks.de/mitglieder/2-arne-drews.html
Registriert seit: 18.03.2015 | Themen: 59 | Beiträge: 364
Bewertung:
14
PHP Selbsteinschätzung: Fortgeschrittene Kenntnisse
09.06.2016, 00:42
Dieser Beitrag wurde zuletzt bearbeitet: 09.06.2016, 00:43 von Arne Drews.
Hi Marc,
Das sieht super aus, danke dafür.
Ich werde mir das morgen mal in Ruhe ansehen, denke aber dass ich damit ans Ziel komme.
Schöne Grüße
https://www.php-rocks.de/mitglieder/28-till.html
Registriert seit: 31.12.2015 | Themen: 49 | Beiträge: 194
Ich bin schlecht in Mathe  Also schlagt mich:
Ist es möglich die Werte irgendwie als 2er Potenzen zu normalisieren und das Prinzip einer Bitmask zu verwenden?
Ansonsten würde ich fürs Brute-forcen die Nummern abwärts sortieren und zunächst versuchen die größten Nummern von der Summe zu substraieren und versuchen auf 0 zu kommen.
Aber ihr habt ja schon eine Lösung, sicherlich besser.
https://www.php-rocks.de/mitglieder/16-mermshaus.html
Registriert seit: 20.03.2015 | Themen: 3 | Beiträge: 50
Bewertung:
6
PHP Selbsteinschätzung: Fortgeschrittene Kenntnisse
15.06.2016, 15:01
Dieser Beitrag wurde zuletzt bearbeitet: 15.06.2016, 15:46 von mermshaus.
Till schrieb:Ist es möglich die Werte irgendwie als 2er Potenzen zu normalisieren und das Prinzip einer Bitmask zu verwenden?
Ich glaube nicht, weil Addition meines Wissens keine „bitwise“-Operation (im Sinne von AND, OR, XOR, …) ist. Die Operationen beachten alle keine Überträge, die bei Addition aber relevant sind.
Zitat:Ansonsten würde ich fürs Brute-forcen die Nummern abwärts sortieren und zunächst versuchen die größten Nummern von der Summe zu substraieren und versuchen auf 0 zu kommen.
Es gibt sicherlich einige Optimierungen zu dem von mir vorgeschlagenen Ansatz. Man könnte zum Beispiel vorab alle Zahlen ausschließen, die größer sind als die gesuchte Summe. Das geht möglicherweise sogar in die Richtung dessen, was du beschreibst.
Ich würde im Zweifel bei Bedarf wirklich erst mal schauen, wie sich Backtracking von der Laufzeit her so macht. Das kann ich ohne weitere Recherche nicht einschätzen. Das sind tendenziell wahrscheinlich Problemstellungen, bei denen ein guter Algorithmus mehr bringt als eine Optimierung eines schlechten Algorithmus, bei denen der richtige Ansatz also entscheidend ist. (Ähnlich wie das Verhältnis von BubbleSort zu QuickSort oder so.) Oft bringt es wenig, Faktoren aus der Laufzeit rauszuziehen, weil ein Zehntel von „viel zu langsam“ immer noch viel zu langsam ist.
Zitat:Aber ihr habt ja schon eine Lösung, sicherlich besser.
Die Lösung ist höchstens „gut genug“. Schnell ist sie nicht gerade. Es hängt letztlich halt auch daran, was der genaue Einsatzzweck ist.
https://www.php-rocks.de/mitglieder/4-tkausl.html
Registriert seit: 19.03.2015 | Themen: 6 | Beiträge: 37
Bewertung:
3
PHP Selbsteinschätzung: Fortgeschrittene Kenntnisse
22.06.2016, 12:14
Dieser Beitrag wurde zuletzt bearbeitet: 22.06.2016, 12:20 von tkausl.
Gebe auch mal meinen Senf dazu ab
http://cpp.sh/2n5q4
Falsche Sprache, ich weiß, tut mir leid.
(Und der Code ist auch nicht der schönste, ist eine 10-minuten spielerei)
Glaube das ist es, was @Till meinte. Von groß nach klein sortieren, dann solange Zahlen (von der grösten beginnend) auf den stack legen bis man entweder die Zahl hat die man sucht oder drüber ist. Ist man drüber nimmt man die oberste Zahl wieder weg und nimmt stattdessen die nächst kleinere zahl. Ist man am Ende der Reihe nimmt man die obersten beiden runter und pusht die nächstkleinere der zweiten, die man runtergenommen hat. wieder drauf.
https://www.php-rocks.de/mitglieder/2-arne-drews.html
Registriert seit: 18.03.2015 | Themen: 59 | Beiträge: 364
Bewertung:
14
PHP Selbsteinschätzung: Fortgeschrittene Kenntnisse
Grundsätzlich ist das nie die falsche Sprache
Danke, das kann ich gut zu C# adaptieren und entsprechend in unserer WaWi zur Verfügung stellen.
Gruß Arne
|