PHP组合数学与排列组合算法

PHP组合数学与排列组合算法排列组合算法在数据处理、密码学、游戏开发等领域都有应用。PHP虽然不是专门做数学计算的语言但实现这些算法也不复杂。先说说排列算法。从n个元素中选取m个考虑顺序。全排列就是n个元素的所有排列方式。php// 全排列function permutations(array $items): array{if (count($items) 1) {return [$items];}$result [];for ($i 0; $i count($items); $i) {$current $items[$i];$remaining array_merge(array_slice($items, 0, $i),array_slice($items, $i 1));foreach (permutations($remaining) as $perm) {array_unshift($perm, $current);$result[] $perm;}}return $result;}$items [1, 2, 3];$result permutations($items);echo 全排列:\n;foreach ($result as $p) {echo . implode(, , $p) . \n;}?组合算法。从n个元素中选m个不考虑顺序。php// 组合function combinations(array $items, int $k): array{if ($k 0) return [[]];if (count($items) $k) return [];$result [];// 包含第一个元素$first $items[0];$rest array_slice($items, 1);foreach (combinations($rest, $k - 1) as $comb) {array_unshift($comb, $first);$result[] $comb;}// 不包含第一个元素foreach (combinations($rest, $k) as $comb) {$result[] $comb;}return $result;}function combinationsIterative(array $items, int $k): array{$n count($items);$result [];// 使用索引组合$indices range(0, $k - 1);while (true) {// 添加当前组合$combination [];foreach ($indices as $index) {$combination[] $items[$index];}$result[] $combination;// 找下一个组合$found false;for ($i $k - 1; $i 0; $i--) {if ($indices[$i] $n - $k $i) {$indices[$i];for ($j $i 1; $j $k; $j) {$indices[$j] $indices[$j - 1] 1;}$found true;break;}}if (!$found) break;}return $result;}$items [A, B, C, D, E];$k 3;echo 从 . count($items) . 个元素中选{$k}个的组合:\n;foreach (combinations($items, $k) as $c) {echo . implode(, , $c) . \n;}echo 组合总数: . count(combinations($items, $k)) . \n;?笛卡尔积是多个集合的所有组合方式php// 笛卡尔积function cartesianProduct(array ...$sets): array{if (empty($sets)) return [[]];$first array_shift($sets);$rest cartesianProduct(...$sets);$result [];foreach ($first as $item) {foreach ($rest as $comb) {array_unshift($comb, $item);$result[] $comb;}}return $result;}$colors [红, 蓝, 绿];$sizes [S, M, L];$materials [棉, 麻];$products cartesianProduct($colors, $sizes, $materials);echo 商品组合: . count($products) . 种\n;foreach ($products as $p) {echo {$p[0]} {$p[1]} {$p[2]}\n;}?子集枚举。n个元素的所有子集个数是2^n。phpfunction subsets(array $items): array{$result [[]];$result[] [];foreach ($items as $item) {$count count($result);for ($i 0; $i $count; $i) {$subset $result[$i];$subset[] $item;$result[] $subset;}}return $result;}function subsetsByBit(array $items): array{$n count($items);$result [];for ($mask 0; $mask (1 $n); $mask) {$subset [];for ($i 0; $i $n; $i) {if ($mask (1 $i)) {$subset[] $items[$i];}}$result[] $subset;}return $result;}$items [A, B, C];echo 所有子集:\n;foreach (subsets($items) as $s) {echo [ . implode(, , $s) . ]\n;}echo 子集总数: . count(subsets($items)) . \n;?组合数学的算法在PHP中实现起来并不复杂。递归和迭代是两种主要的方式递归代码简洁但要注意性能迭代代码稍复杂但效率高。理解这些算法不光是为了面试在实际项目中做数据分析、测试用例生成或者排列组合类功能时都能用上。