Code Coverage |
||||||||||
Classes and Traits |
Functions and Methods |
Lines |
||||||||
| Total | |
100.00% |
1 / 1 |
|
100.00% |
2 / 2 |
CRAP | |
100.00% |
47 / 47 |
| Permutation | |
100.00% |
1 / 1 |
|
100.00% |
2 / 2 |
20 | |
100.00% |
47 / 47 |
| permutationsCount | |
100.00% |
1 / 1 |
8 | |
100.00% |
12 / 12 |
|||
| permutations | |
100.00% |
1 / 1 |
12 | |
100.00% |
35 / 35 |
|||
| <?php | |
| namespace ia\Math; | |
| use \Generator; | |
| /** | |
| * Permutation of items ['a','b'] => [ ['a','b'], ['b', 'a'] ] | |
| * | |
| */ | |
| class Permutation { | |
| /** | |
| * Number of permuations for $numberOfElements in groups of $numberInPermutation length | |
| * | |
| * @param int $numberOfElements | |
| * @param int $numberInPermutation | |
| * @return int number of permutations, 0 in imposible permutations | |
| */ | |
| public static function permutationsCount($numberOfElements, $numberInPermutation = null) { | |
| // // permutationsCount = n!/(n-k)! = =n(n-1) (n-2)(n-3).....(n-r+1) | |
| if ($numberInPermutation === null) { | |
| $numberInPermutation = $numberOfElements; | |
| } | |
| if($numberInPermutation <= 0 || $numberInPermutation > $numberOfElements || $numberOfElements <= 0) { | |
| return 0; | |
| } | |
| if($numberInPermutation === $numberOfElements) { | |
| return Math::factorial($numberOfElements); | |
| } | |
| if($numberOfElements <= 20) { | |
| return Math::factorial($numberOfElements)/Math::factorial($numberOfElements - $numberInPermutation); | |
| } | |
| $numberOfPermutations = $numberOfElements; | |
| for($i=$numberOfElements-1, $limit = $numberOfElements - $numberInPermutation + 1; $i>=$limit; $i--) { | |
| $numberOfPermutations *= $i; | |
| } | |
| return $numberOfPermutations; | |
| } | |
| /** | |
| * Permuations for $numberOfElements in groups of $numberInPermutation length | |
| * foreach (permutations(['a', 'b','c'],2) as $permutation) echo " | ".implode(',', $permutation); = | a,b | a,c | b,a | b,c | c,a | c,b | |
| * | |
| * @param array $set | |
| * @param int $numberInPermutation, null sets to count($set) | |
| * @return Generator, empty on imposible permutations | |
| */ | |
| public static function permutations($set, $numberInPermutation = null) { | |
| $set = array_values($set); | |
| $n = count($set); | |
| if ($numberInPermutation === null) { | |
| $numberInPermutation = $n; | |
| } | |
| if ($numberInPermutation > $n || $numberInPermutation<=0 || $n <= 0) { | |
| return; | |
| } | |
| $indices = range(0, $n - 1); | |
| $cycles = range($n, $n - $numberInPermutation + 1, -1); // count down | |
| yield array_slice($set, 0, $numberInPermutation); | |
| while(true) { | |
| $exit_early = false; | |
| for($i = $numberInPermutation; $i--; $i >= 0) { | |
| $cycles[$i] -= 1; | |
| if ($cycles[$i] === 0) { | |
| // Push whatever is at index $i to the end, move everything back | |
| if ($i < count($indices)) { | |
| $removed = array_splice($indices, $i, 1); | |
| array_push($indices, $removed[0]); | |
| } | |
| $cycles[$i] = $n - $i; | |
| } else { | |
| $j = $cycles[$i]; | |
| // Swap indices $i & -$j. | |
| $i_val = $indices[$i]; | |
| $neg_j_val = $indices[count($indices) - $j]; | |
| $indices[$i] = $neg_j_val; | |
| $indices[count($indices) - $j] = $i_val; | |
| $result = []; | |
| $counter = 0; | |
| foreach ($indices as $indx) { | |
| array_push($result, $set[$indx]); | |
| $counter++; | |
| if ($counter == $numberInPermutation) break; | |
| } | |
| yield $result; | |
| $exit_early = true; | |
| break; | |
| } | |
| } | |
| if (!$exit_early) { | |
| break; // Outer while loop | |
| } | |
| } | |
| } | |
| } |