多个不同长度数组对比取得n个不重复组合
时间: 2023-06-24 16:06:55 浏览: 43
可以使用回溯算法来解决这个问题。具体步骤如下:
1. 定义一个变量 `n` 表示要取得的组合数量,以及一个列表 `res` 用于存储结果。
2. 定义一个递归函数 `backtrack(comb, idx)`,其中 `comb` 表示当前已经组合的元素,`idx` 表示当前处理的数组的下标。
3. 如果 `len(comb) == n`,说明已经取得了足够的组合,将 `comb` 添加到 `res` 中并返回。
4. 如果 `idx == len(arr)`,说明当前数组已经处理完毕,直接返回。
5. 在当前数组中循环遍历,每次将当前元素添加到 `comb` 中,并递归调用 `backtrack(comb, idx+1)` 处理下一个数组。
6. 在递归调用返回后,将 `comb` 中最后一个元素删除,继续遍历下一个元素进行回溯。
下面是基于 Python 的回溯算法实现:
```python
def combine(arrs, n):
res = []
def backtrack(comb, idx):
if len(comb) == n:
res.append(comb[:])
return
if idx == len(arrs):
return
for i in range(len(arrs[idx])):
comb.append(arrs[idx][i])
backtrack(comb, idx+1)
comb.pop()
backtrack([], 0)
return res
```
其中 `arrs` 是一个包含多个数组的列表,`n` 表示要取得的组合数量。调用示例:
```python
arrs = [[1,2,3], [4,5], [6,7,8,9]]
n = 3
res = combine(arrs, n)
print(res) # [[1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 6], [1, 5, 7], [1, 5, 8], [1, 5, 9], [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 6], [2, 5, 7], [2, 5, 8], [2, 5, 9], [3, 4, 6], [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 5, 6], [3, 5, 7], [3, 5, 8], [3, 5, 9]]
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)