drupol/phpermutations

Generate Permutations and Combinations in an efficient way.

PHPermutations

PHP Iterators and Generators to generate combinations and permutations in an efficient way.

At first the library was created to only generate permutations and combinations.

In the end, I added other Iterators and Generators like:

• Fibonacci numbers,
• Perfect numbers,
• Prime numbers,
• Product of numbers,
• Rotation of an array,
• Cycling through an array,
• Permutations,
• Combinations,

Introduction

I've always been fascinated by numbers and everything around them... in other words, mathematics.

The library has been written first for being used in PHPartition, then it has been extended here and there.

Its main use is for generating Permutations and Combinations without running out of memory, thanks to PHP Generators and and Iterators.

The difference with other combinatorics library is that you can use an extra parameter 'length', that allows you to compute Permutations and Combinations of a particular size. The other notable difference is that your input arrays may contains any type of object (integers, arrays, strings or objects), the library will still continue to work without any trouble.

Requirements

• PHP >= 7.1.3,

How to use

Include this library in your project by doing:

composer require drupol/phpermutations

Let's say you want to find all the permutations of the list of number [1, 2, 3, 4, 5] having a length of 3:

// Create the object
$permutations = new \drupol\phpermutations\Generators\Permutations([1,2,3,4,5], 3);

// Use a foreach loop.
foreach ($permutations->generator() as $permutation) {// do stuff}

// Or get the whole array at once.
$permutations->toArray();

Most of the components always has the same arguments except for very few of them.

As the documentation per component is not written yet, I advise you to check the tests to see how to use them.

Combinations

In mathematics, a combination is a way of selecting items from a collection, such that (unlike permutations) the order of selection does not matter. -- Wikipedia

In one sentence: When the order doesn't matter, it is a Combination.

Examples

Let's say we have a group of fruits:

$list = ['Apple', 'Pear', 'Banana', 'Orange']

and we want to find the combinations of length: 3, the result will be:

['Apple', 'Pear', 'Banana']

['Apple', 'Pear', 'Orange']

['Apple', 'Banana', 'Orange']

['Pear', 'Banana', 'Orange']

Permutations

In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. These differ from combinations, which are selections of some members of a set where order is disregarded. -- Wikipedia

In one sentence: When the order does matter, it is a Permutation.

Examples

Let's say we have a group of fruits

['Apple', 'Pear', 'Banana', 'Orange']

and we want to find the permutations of length: 3, the result will be:

['Apple', 'Pear', 'Banana']

['Pear', 'Apple', 'Banana']

['Apple', 'Banana', 'Pear']

['Banana', 'Apple', 'Pear']

['Pear', 'Banana', 'Apple']

['Banana', 'Pear', 'Apple']

['Apple', 'Pear', 'Orange']

['Pear', 'Apple', 'Orange']

['Apple', 'Orange', 'Pear']

['Orange', 'Apple', 'Pear']

['Pear', 'Orange', 'Apple']

['Orange', 'Pear', 'Apple']

['Apple', 'Banana', 'Orange']

['Banana', 'Apple', 'Orange']

['Apple', 'Orange', 'Banana']

['Orange', 'Apple', 'Banana']

['Banana', 'Orange', 'Apple']

['Orange', 'Banana', 'Apple']

['Pear', 'Banana', 'Orange']

['Banana', 'Pear', 'Orange']

['Pear', 'Orange', 'Banana']

['Orange', 'Pear', 'Banana']

['Banana', 'Orange', 'Pear']

['Orange', 'Banana', 'Pear']

The permutations of length 3 of the array [1, 2, 3, 4, 5] are, please hold on tight, the sum of all the permutations of each combinations having a length of 3 of that array.

Tests

Each Generators and Iterators are tested using the same values as input. I try to be as much complete as possible with the tests. Every time the sources are modified, Github, the continuous integration service, tests the code against those tests, this way you are aware if the changes that you are introducing are valid.

Contributing

Feel free to contribute to this library by sending Github pull requests. I'm quite reactive :-)

phpermutations's Issues

Permutations without repitation

How to get permutations without repitations?
array(1,2,3,4,5,6)
all perms for 3: example: 1,2,3 1,2,4 etc

Deprecation Notices in PHP 8.3

Hi,

Running PHP 8.3.0:

PHP 8.3.0 (cli) (built: Nov 21 2023 17:48:31) (ZTS Visual C++ 2019 x64)

I am getting Deprecation notices when trying to fetch combinations using the following code:

$galaxyIDs = array_keys($galaxies);
print_r($galaxyIDs);

$galaxyCombinations = new Combinations($galaxyIDs, 2);
print_r($galaxyCombinations->toArray());

The output of the code is:

Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 6
    [6] => 7
    [7] => 8
    [8] => 9
)

Deprecated: Return type of drupol\phpermutations\Combinatorics::count() should either be compatible with Countable::count(): int, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in C:\Development\AdventOfCode2023\vendor\drupol\phpermutations\src\Combinatorics.php on line 53

Deprecated: Return type of drupol\phpermutations\Iterators::current() should either be compatible with Iterator::current(): mixed, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in C:\Development\AdventOfCode2023\vendor\drupol\phpermutations\src\Iterators.php on line 26

Deprecated: Return type of drupol\phpermutations\Iterators::key() should either be compatible with Iterator::key(): mixed, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in C:\Development\AdventOfCode2023\vendor\drupol\phpermutations\src\Iterators.php on line 34

Deprecated: Return type of drupol\phpermutations\Iterators::rewind() should either be compatible with Iterator::rewind(): void, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in C:\Development\AdventOfCode2023\vendor\drupol\phpermutations\src\Iterators.php on line 44

Deprecated: Return type of drupol\phpermutations\Iterators\Combinations::next() should either be compatible with Iterator::next(): void, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in C:\Development\AdventOfCode2023\vendor\drupol\phpermutations\src\Iterators\Combinations.php on line 65

Deprecated: Return type of drupol\phpermutations\Iterators\Combinations::valid() should either be compatible with Iterator::valid(): bool, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in C:\Development\AdventOfCode2023\vendor\drupol\phpermutations\src\Iterators\Combinations.php on line 88

Enable grumphp.

Update the documentation

Permutations with Repetition

Firstly, thanks for this library.

I would like to know if there is a way to get Permutations with Repetition.

Convert src\Permutations into a PHP Generator.

Thanks to the help of @markwilson, we can use a PHP Generator to generate the permutations of an array, of any length.

Now that we have that, convert the class in src\Permutations.php in a proper PHP Generator.

Question on usage

Would i be able to utilize this library to determine all the combinations of x items into y groups?
For example, if I had 2 items [1, 2] with 2 groups, the 4 possibilities would be:

1. [ 1,2 ] [ ]
2. [ 1 ] [ 2 ]
3. [ 2 ] [ 1 ]
4. [ ] [ 1,2 ]

Thanks in advance!

Add a Rotation iterator.

Fix PHPCS

Count combinations returns NAN

Consider using bcmath in factorial calculations.
This code results in NAN

$p = new Combinations(range(1, 200), 2);
var_dump($p->count());

While this code results in 19900

$p = new Combinations(range(1, 200), 2);
var_dump(count($p->toArray()));

PSR2 coding standard