Last active
December 17, 2023 00:48
-
-
Save macocci7/0933e2c02cafb13cbe9286328ec8fe4d to your computer and use it in GitHub Desktop.
2進数を使って全ての組み合わせを取得する関数。A function to get all combinations using binary numbers.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <?php | |
| /** | |
| * Code to get all combinations of array elements | |
| */ | |
| namespace Macocci7; | |
| class Combination | |
| { | |
| /** | |
| * returns system bit | |
| * @param | |
| * @return int | |
| */ | |
| public static function systemBit(): int | |
| { | |
| // PHP_INT_ISZE: | |
| // - 32bit-system: 4 (bytes) | |
| // - 64bit-system: 8 (bytes) | |
| return PHP_INT_SIZE * 8; | |
| } | |
| /** | |
| * returns all combinations | |
| * @param array $items | |
| * @param bool $sort = false | |
| * @return array | |
| */ | |
| public function all(array $items, bool $sort = false) | |
| { | |
| $count = count($items); | |
| if (0 === $count) { | |
| throw new \Exception("Empty array set."); | |
| } | |
| if ($count >= $this->systemBit() - 1) { | |
| throw new \Exception("Too many elements."); | |
| } | |
| $numberOfAllPatterns = 2 ** $count; | |
| $format = '%0' . $count . 'b'; | |
| $combinations = []; | |
| for ($i = $numberOfAllPatterns - 1; $i > 0; $i--) { | |
| $combination = []; | |
| foreach (str_split(sprintf($format, $i)) as $index => $bit) { | |
| if ((bool) $bit) { | |
| $combination[] = $items[$index]; | |
| } | |
| } | |
| $combinations[] = $combination; | |
| } | |
| if ($sort) { | |
| $strs = array_map(fn ($c): string => implode(',', $c), $combinations); | |
| array_multisort($strs, SORT_ASC, SORT_STRING, $combinations); | |
| } | |
| return $combinations; | |
| } | |
| } | |
| // Starting operation | |
| $start = microtime(true); | |
| $items = ['A', 'B', 'C', 'D', 'E']; | |
| $sort = false; | |
| $c = new Combination(); | |
| foreach ($c->all($items, $sort) as $index => $combination) { | |
| echo sprintf("(%s)\n", implode(', ', $combination)); | |
| } | |
| echo sprintf( | |
| "Time: %.6f sec / Peak Memory: %.3f MB\n", | |
| microtime(true) - $start, | |
| memory_get_peak_usage(true) / 1024 / 1024 | |
| ); |
Changing the sorting flag
$sort = true;results in:
$ php -f getAllCombinations.php
(A)
(A, B)
(A, B, C)
(A, B, C, D)
(A, B, C, D, E)
(A, B, C, E)
(A, B, D)
(A, B, D, E)
(A, B, E)
(A, C)
(A, C, D)
(A, C, D, E)
(A, C, E)
(A, D)
(A, D, E)
(A, E)
(B)
(B, C)
(B, C, D)
(B, C, D, E)
(B, C, E)
(B, D)
(B, D, E)
(B, E)
(C)
(C, D)
(C, D, E)
(C, E)
(D)
(D, E)
(E)
Time: 0.000461 sec / Peak Memory: 2.000 MB
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This code results in: