, (*1)
COMBINATORICS
Wikipedia : Combinatorics is a branch of mathematics
concerning the study of finite or countable discrete structures. Aspects of combinatorics include
counting the structures of a given kind and size (enumerative combinatorics), deciding when certain
criteria can be met, and constructing and analyzing objects meeting the criteria (as in combinatorial
designs and matroid theory), finding "largest", "smallest", or "optimal" objects (extremal
combinatorics and combinatorial optimization), and studying combinatorial structures arising in an
algebraic context, or applying algebraic techniques to combinatorial problems (algebraic combinatorics)., (*2)
Requirements
PHP 5.4+ is required. (_The [] short array syntax was introduced on 5.4_), (*3)
Disclosure
The Combination and Permutation implementation is based on the work of _David Sanders_ (shangxiao@php.net)., (*4)
Changelog
- 1.0 Added Permutations code (with unit tests)
- 0.2 Unit Tests added to Combinations library.
- 0.1 Port of the Combinations library (manual tests done, but unit tests, need to be added).
Classes
Combinations
This version is similar to David's with the difference that the base method will return all possible
combinations based on the supplied set., (*5)
It also provides with a Static method to access the class as a utility, so if you need this functionality
very often, use the Instance approach for you'll get better performance, but if you use it here and
there, the static access may prove more readable., (*6)
Additionally, it detaches the Pointers functionality into it's own class, providing a bit more
clarity into the Combinations code as well as making it better thread-safe as the pointers are no
longer an attribute of the class shared across the methods, it is an object created for each run and
thus allowing to run multiple combinations in parallel from the same class instance without having
them interfere with each other., (*7)
Note: As with David's implementation, the returned combinations preserve the keys supplied. (However
fixes a minor bug where the single element combinations would not preserve its keys), (*8)
Permutations
As in Combinations, this code is similar to David's with the difference that both pieces are not mixed
in the same class, Permutations is a class of its own and has an internal reference to the Combinations class., (*9)
It as well, provides with a Static method to access the class as a utility., (*10)
Usage
This usage considers that you have an autoloader running. (see Install for more reference), (*11)
The result of the functionality is an Array of Arrays in which the Outer Array is a list of combinations and each Inner Array is the combination itself., (*12)
Retrieving all combinations for a source data set.
$sourceDataSet = ['a' => 5, 'b' => 6, 'c' => 8, 'd' => 10];
// Retrieve all combinations as Utility
$combinationsList = \Math\Combinatorics\Combination::get($sourceDataSet);
// Retrieve all combinations as instance class
$combination = new \Math\Combinatorics\Combination();
$combinationsList = $combination->getCombinations($sourceDataSet);
Here is a detailed version of the expanded array, (*13)
size 1: [`a` => 5] [`b` => 6] [`c` => 8] [`d` => 10]
size 2: [`a` => 5,`b` => 6] [`a` => 5,`c` => 8]
[`a` => 5,`d` => 10] [`b` => 6,`c` => 8]
[`b` => 6,`d` => 10] [`c` => 8,`d` => 10]
size 3: [`a` => 5,`b` => 6,`c` => 8]
[`a` => 5,`b` => 6,`d` => 10]
[`a` => 5,`c` => 8,`d` => 10]
[`b` => 6,`c` => 8,`d` => 10]
size 4: [`a` => 5,`b` => 6,`c` => 8,`d` => 10]
Retrieving combinations of a given length for a source data set.
$sourceDataSet = ['a' => 5, 'b' => 6, 'c' => 8, 'd' => 10];
// Retrieve all combinations as Utility
$combinationsList = \Math\Combinatorics\Combination::get($sourceDataSet, 3);
// Retrieve all combinations as instance class
$combination = new \Math\Combinatorics\Combination();
$combinationsList = $combination->getCombinations($sourceDataSet, 3);
Here is a detailed version of the expanded array, (*14)
size 3: [`a` => 5,`b` => 6,`c` => 8]
[`a` => 5,`b` => 6,`d` => 10]
[`a` => 5,`c` => 8,`d` => 10]
[`b` => 6,`c` => 8,`d` => 10]
Retrieving all permutations for a source data set.
$sourceDataSet = ['z' => 10, 'a' => 50, 'x' => 77];
// Retrieve all combinations as Utility
$permtuationList = \Math\Combinatorics\Permutation::get($sourceDataSet);
// Retrieve all combinations as instance class
$permutation = new \Math\Combinatorics\Permutation();
$permutationsList = $permutation->getPermutations($sourceDataSet);
Here is a detailed version of the expanded array, (*15)
size 1: ['z' => 10]
['a' => 50]
['x' => 77]
size 2: ['z' => 10, 'a' => 50]
['a' => 50, 'z' => 10]
['z' => 10, 'x' => 77]
['x' => 77, 'z' => 10]
['a' => 50, 'x' => 77]
['x' => 77, 'a' => 50]
size 3: ['z' => 10, 'a' => 50, 'x' => 77]
['z' => 10, 'x' => 77, 'a' => 50]
['a' => 50, 'x' => 77, 'z' => 10]
['a' => 50, 'z' => 10, 'x' => 77]
['x' => 77, 'z' => 10, 'a' => 50]
['x' => 77, 'a' => 50, 'z' => 10]
Retrieving permutations of a given length for a source data set.
$sourceDataSet = ['z' => 10, 'a' => 50, 'x' => 77];
// Retrieve all combinations as Utility
$permtuationList = \Math\Combinatorics\Permutation::get($sourceDataSet, 2);
// Retrieve all combinations as instance class
$permutation = new \Math\Combinatorics\Permutation();
$permutationsList = $permutation->getPermutations($sourceDataSet, 2);
Here is a detailed version of the expanded array, (*16)
size 2: ['z' => 10, 'a' => 50]
['a' => 50, 'z' => 10]
['z' => 10, 'x' => 77]
['x' => 77, 'z' => 10]
['a' => 50, 'x' => 77]
['x' => 77, 'a' => 50]
Install
The easiest way to install is through composer., (*17)
Just create a composer.json file for your project:, (*18)
{
"require": {
"alphazygma/combinatorics": "~1.0"
}
}
Then you can run these two commands to install it:, (*19)
$ curl -s http://getcomposer.org/installer | php
$ php composer.phar install
or simply run composer install if you have have already installed the composer globally., (*20)
Then you can include the autoloader, and you will have access to the library classes:, (*21)
<?php
require 'vendor/autoload.php';
Wallogit.com
