mistralys / subsetsum
PHP SubsetSum implementation to search for number combinations.
Requires
- php: >=7.1
- ext-bcmath: *
Requires (Dev)
- phpstan/phpstan: >=0.12
- phpunit/phpunit: >=8.5
This package is auto-updated.
Last update: 2024-10-29 05:53:51 UTC
README
PHP SubsetSum implementation
Given a target number and a list of numbers, determines which number combinations equal the target number.
For example: With 25
as the target number, and 10
, 5
, 15
as the numbers list, this will determine that 25 = 10 + 15
.
Requirements
- PHP >= 7.1
- BCMath extension
Installation
Require the package via composer on the command line:
composer require mistralys/subsetsum
Or edit composer.json directly:
"require":
{
"mistralys/subsetsum": "dev-master"
}
Usage
The create
method is used to create a new instance, which can be used to retrieve matches, or to configure options:
$sub = SubsetSum::create(25, array(5,10,7,3,20));
Checking if there are any matches
Some methods like getShortestMatch()
can return null, so it's best to check if there are matches beforehand.
if(!$sub->hasMatches()) { echo 'No matches.'; }
Getting all matches
To retrieve all matching number combinations:
$matches = $sub->getMatches();
This will return an array like this:
array( array(3, 5, 7, 10), array(5, 20) )
NOTE: The numbers in each match result are always sorted in ascending order.
Getting the shortest match
The shortest match is the one that uses the least amount of number combinations.
// check if there are matches, since the method can return null. if($sub->hasMatches()) { $match = $sub->getShortestMatch(); }
In the example, this would return the following match array:
array(5, 20)
Getting the longest match
The longest match is the one that uses the highest amount of number combinations.
// check if there are matches, since the method can return null. if($sub->hasMatches()) { $match = $sub->getLongestMatch(); }
In the example, this would return the following match array:
array(3, 5, 7, 10)
Adjusting the amount of decimals & rounding
By default, the internal calculations will round the numbers to 2
decimals, using PHP's default "round up half" rounding. This can be easily adjusted to your needs:
// 4 decimals, default rounding mode $sub->setPrecision(4); // 1 decimal, specific rounding mode $sub->setPrecision(1, PHP_ROUND_HALF_DOWN);
The full list of possible modes can be found here:
http://www.php.net/manual/en/math.constants.php
Working with integers
Working in integer mode simply means using a precision of 0
.
$sub->makeInteger();
NOTE: The match arrays will contain integers, but which are still typed as floats. You will have to cast them to int
as needed.
Performance
A word of caution: calculating subset sums has an exponential complexity the higher the amount of numbers to search through. You can easily bring your server to your knees with larger sets, so I would recommend setting some limits on the amount of numbers in your application.
Credits
The initial mechanism was inspired by this answer on StackOverflow:
There is also another interesting package that goes further than this: