n个数组排列组合

第一次收到邀请回答。。不过今天才看到代码我就用php写了，带注释，这个题目一看排列组合，我能想到的就是递归搜索了，以下仅为一种参考解法，并非最优对这样的数组取n个元素进行排列组合[[3.5],[4.6,23],[5.25,13]]，我把这个问题拆分成2步，一是对这个二维数组（简称 a）任取 n 个子一维数组组成一个新的二维数组（简称 b)，然后对 b 进行任取 n 个元素的操作，这时就是对 b 中每一个子一维数组中任取一个元素，组在一起即为题解。例： a = [[3.5],[4.6,23],[5.25,13]] n = 2此时 b 有3个，分别为 b1 = [[3.5], [4.6,23]] b2 = [[3.5], [5.25, 13]] b3 = [[4.6, 23], [5.25, 13]]再对每个 b 中每一个子一维数组中任取一个元素，组在一起即为题解对 b1 【3.5,4.6,】，【3.5,23】，对 b2 【3.5,5.25】，【3.5,13】，对 b3 【4.6,5.25】，【4.6,13】，【23,5.25】，【23,13】一下是参考代码（2 步都是用递归做的）：<?php // 此函数作用：任取 a 中 n 个子一维数组，组成 b function aofn($a, $b, $n) { // 递归终止条件，每次递归 n - 1, 当 n 为 0 时说明以找到 n 个子一维数组 //然后把组成的 b 作为第二步函数的参数传进去 if($n == 0) { $c = array(); // var_dump($b); test($b, $c, count($b)); return ; } for($i = 0; $i < count($a); $i ++) { // 每次取得子一维数组放到 b 中 $b[] = $a[$i]; //array_slice($a, $i+1) ：取 a 中索引从 $i+1 位置的数组到最后组成一个新数组 //因为像 1,2 和 2,1这种是相等的，所有直接往后取 aofn(array_slice($a, $i+1), $b, $n - 1); // 每次搜索完记得移除 b 上面添加的那个子数组，继续下一次搜索 array_pop($b); } } // 注意一下两个函数的参数位置关系，第一个函数中的 $b 变成了这里的 $a， // 这里的 $b 是一个空一维数组 ; //此函数作用：再对每个 a 中每一个子一维数组中任取一个元素，组在一起 function test($a, $b, $n) { // 这里终止条件跟上面函数差不多，每次找一个，找到 n 个终止，继续找下一轮 if($n == 0) { // 输出找到存起来的元素 foreach($b as $k) { echo $k.' '; } echo "\n"; return ; } //这里就是每次去一个子数组出来，b每次存子数组中的一个元素，递归完就全部取完了 for($i = 0; $i < count($a[0]); $i ++) { //移除 a 的第一个子数组 $arr = array_shift($a); $b[] = $arr[$i]; test($a, $b, $n-1); // 每次搜索完记得移除 b 上面添加的那个子元素，继续下一次搜索 array_pop($b); // 每次搜索完记得加入 a 上面移除的那个子数组(这个函数是添加到头部)， //继续下一次搜索 array_unshift($a, $arr); } } //代码没有写判断不合法输入，只要输入正常，输出是没问题的，以下是测试用例 //注意：因为是递归写的，相对费时，所以不能测试较大的数据量 $a = array([3.5], [4.6, 23], [5.25, 13]); $b = array(); $n = 2; aofn($a, $b, $n);

n个数组排列组合

1回答