需求:
在rpg游戏中,游戏各种配置非常复杂,例如:有一个奖励池A,B,C,D,可以根据配置的奖品数量3,从奖品池中随机取出对应数量的商品,这些商品的组合可能是:AAA,AAB,ABB,ABC,BCD…这就需要实现一个排列组合算法。
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 |
<?php /** * 排列组合算法 * @author by vonnwang * @date 2019/08/19 */ class arrangeCombination { /** * 递归实现排列算法 * * @param array $sort 要进行排列的数组 * @param int $num 要取的元素个数 * @return array $result 排列可能性的数组 * */ public function arrange($a, $m) { $r = array(); $n = count($a); if ($m <= 0 || $m > $n) { return $r; } for ($i=0; $i<$n; $i++) { $b = $a; $t = array_splice($b, $i, 1); if ($m == 1) { $r[] = $t; } else { $c = self::arrange($b, $m-1); foreach ($c as $v) { $r[] = array_merge($t, $v); } } } return $r; } /** * 循环将二维数组每个元素字符进行顺序组合 * * @author Sharif * * @since 2015-09-22 * @param array $data 需要进行组合的数组 * @param array $part 已部分整合的数组 * @return array $result 整理后的数组 * */ public function arrayCombination($data,$part=array()) { //数据已经存在 if ( is_array($part) && count($part) > 0 ) { foreach ( $part as $v ) { foreach ( $data as $val ) { $result[] = $v.','.$val; } } } else { //首次进入进行赋值 $result = $data; } return $result; } /** * 递归将二维数组每个元素字符进行顺序组合 * * @author Sharif * * @since 2015-09-22 * @param array $arr 需要进行组合的数组 * @param int $level 获取元素的键 * @return array $arr 整理后的数组 * */ public function bulidArrayCombination(&$arr,$level=0) { $all = count($arr)-2; $data = $arr[$level]; $tmp = array(); //数据已经存在 if ( is_array($arr['res']) && count($arr['res']) > 0 ) { foreach ( $arr['res'] as $k=>$v ) { foreach ( $data as $val ) { $tmp[] = $v.','.$val; } } } else { //首次进入进行赋值 $tmp = $data; } $arr['res'] = $tmp; //递归调用 if ( $all != $level ) { $level = $level+1; $this->bulidArrayCombination($arr,$level); } return $arr; } /** * 求数组的组合 * * @author vonnwang * @since 2019/08/19 * * @param array $sort 要进行组合的数组 * @param int $num 要取的元素 * @return array $result 组合后的数组 * */ public function combination($sort, $num) { $result = $data = array(); if ( $num == 1 ) { return $sort; } foreach ( $sort as $k=>$v ) { unset($sort[$k]); $data = $this->combination($sort,$num-1); foreach ($data as $row) { $result[] = $v.$row; } } return $result; } } $obj = new arrangeCombination(); $arr = array('A','B','C'); $res = $obj->arrange($arr,2); print_r($res); //需要进行组合的二维数组定义 $arr = array( array('A','B'), array('C','D'), array('E','F'), ); $result = array(); //构造返回数组 foreach ( $arr as &$val ) { $result = $obj->arrayCombination($val,$result); } print_r($result); //需要进行组合的二维数组定义 //res的key必须存在 $arr = array( array('A','B'), array('C','D'), array('E','F'), array('G','H'), 'res' => array(), ); //构造返回数组 $res = $obj->bulidArrayCombination($arr); print_r($res); $arr = array('A','B','C'); //这个是组合 $res = $obj->combination($arr,2); print_r($res); |
打印结果:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 |
Array ( [0] => Array ( [0] => A [1] => B [2] => C ) [1] => Array ( [0] => A [1] => B [2] => D ) [2] => Array ( [0] => A [1] => C [2] => B ) [3] => Array ( [0] => A [1] => C [2] => D ) [4] => Array ( [0] => A [1] => D [2] => B ) [5] => Array ( [0] => A [1] => D [2] => C ) [6] => Array ( [0] => B [1] => A [2] => C ) [7] => Array ( [0] => B [1] => A [2] => D ) [8] => Array ( [0] => B [1] => C [2] => A ) [9] => Array ( [0] => B [1] => C [2] => D ) [10] => Array ( [0] => B [1] => D [2] => A ) [11] => Array ( [0] => B [1] => D [2] => C ) [12] => Array ( [0] => C [1] => A [2] => B ) [13] => Array ( [0] => C [1] => A [2] => D ) [14] => Array ( [0] => C [1] => B [2] => A ) [15] => Array ( [0] => C [1] => B [2] => D ) [16] => Array ( [0] => C [1] => D [2] => A ) [17] => Array ( [0] => C [1] => D [2] => B ) [18] => Array ( [0] => D [1] => A [2] => B ) [19] => Array ( [0] => D [1] => A [2] => C ) [20] => Array ( [0] => D [1] => B [2] => A ) [21] => Array ( [0] => D [1] => B [2] => C ) [22] => Array ( [0] => D [1] => C [2] => A ) [23] => Array ( [0] => D [1] => C [2] => B ) ) 12 Array ( [0] => Array ( [0] => A [1] => B [2] => C ) [1] => Array ( [0] => A [1] => B [2] => D ) [2] => Array ( [0] => A [1] => C [2] => D ) [3] => Array ( [0] => B [1] => C [2] => D ) ) 6 |