n个数组排列组合

Question

对这样的数组取n个元素进行排列组合[[3.5],[4.6,23],[5.25,13]]想要的结果：1、取两个排列的时候【3.5,4.6,】，【3.5,23】，【3.5,5.25】，【3.5,13】，【4.6,5.25】，【4.6,13】，【23,5.25】，【23,13】2、取三个排列的时候【3.5,4.6,5.25】，【3.5,4.6,13】，【3.5,23,5.25】，【3.5,23,13】

Answer 1

第一次收到邀请回答。。不过今天才看到

代码我就用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);