Permutations and big arrays in PHP - performance issues

user_18384995 0
Viewed 122

I have an array of numbers (int or float) and I need to find a value by combining array values. Once the smallest possible combination is found the function returns the array values. Therefore I start with sample-size=1 and keep incrementing it.

Here's a simplified example of the given data:

$values = [10, 20, 30, 40, 50];
$lookingFor = 80;

Valid outcomes:

[30, 50] // return this
[10, 20, 50], [10, 30, 40] // just to demonstrate the possible combinations

Permutations solve this problem and I've tried many different implementations (for example: Permutations - all possible sets of numbers, Get all permutations of a PHP array?, https://github.com/drupol/phpermutations). My favourite is this one with a parameter for permutation-size using the Generator pattern: https://stackoverflow.com/a/43307800

What's my problem? Performance! My arrays have 5 - 150 numbers and sometimes the sum of 30 array numbers is needed to find the searched value. Sometimes the value can't be found, which means I needed to try all possible combinations. Basically with permutation-size > 5 the task becomes too time consuming.

An alternative, yet not precise way is to sort the array, take the first X and last X numbers and compare with the searched value. Like this:

sort($values, SORT_NUMERIC);
$countValues = count($values);

if ($sampleSize > $countValues)
{
    $sampleSize = $countValues;
}

$minValues = array_slice($values, 0, $sampleSize);
$maxValues = array_slice($values, $countValues - $sampleSize, $sampleSize);

$possibleMin = array_sum($minValues);
$possibleMax = array_sum($maxValues);

if ($possibleMin === $lookingFor)
{
    return $minValues;
}

if ($possibleMax === $lookingFor)
{
    return $maxValues;
}

return [];

Hopefully somebody has dealt with a similar problem and can guide me in the right direction. Thank you!

permutation math arrays php
1 Answers

  • you must use combination instead of permutations {ex: P(15) = 130767436800 vs C(15) = 32768}

  • if array_sum < target_number then no solution exists

  • if in_array(target_number, numbers) solution found with 1 element

  • sort lowest to highest

  • start with C(n,2) where 2 represents 1st 2nd then 1st 3rd etc (static one is 1st element)

  • if above loop found no solution continue with 2nd 3rd then 2nd 4th, etc)

  • if C(n,2) had no solution then jump to C(n,3)s but this time 2 static numbers and 1 dynamic one

  • if loop ended with no solution then there exists no solution

lastly, I would adjust this question and ask in statistics branch of stack exchange (crossvalidated) since mean, median and cumulative distribution of the sums of the numbers may hint to decrease the number of iterations significantly and this is their profession.

user_183067880
Related