用递归函数或使用堆栈生成排列组合数。测试用例: 1) {A, B, C, D, E, F, G, H}中任取三个元素的组合数
时间: 2023-10-02 12:10:16 浏览: 45
1. 递归函数实现:
```python
def combinations(lst, k):
"""
递归函数生成lst中任取k个元素的组合数
:param lst: 列表
:param k: 选取元素个数
"""
if k == 0:
# 若选取元素个数为0,则返回空列表
return [[]]
if k > len(lst):
# 若选取元素个数大于列表长度,则返回空列表
return []
# 选取第一个元素,生成剩下的k-1个元素的组合数
result = [[lst[0]] + item for item in combinations(lst[1:], k-1)]
# 不选第一个元素,生成剩下的k个元素的组合数
result += combinations(lst[1:], k)
return result
# 测试用例
lst = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
k = 3
print(combinations(lst, k))
```
输出:
```
[['A', 'B', 'C'], ['A', 'B', 'D'], ['A', 'B', 'E'], ['A', 'B', 'F'], ['A', 'B', 'G'], ['A', 'B', 'H'], ['A', 'C', 'D'], ['A', 'C', 'E'], ['A', 'C', 'F'], ['A', 'C', 'G'], ['A', 'C', 'H'], ['A', 'D', 'E'], ['A', 'D', 'F'], ['A', 'D', 'G'], ['A', 'D',...```
2. 使用堆栈实现:
```python
def combinations(lst, k):
"""
使用堆栈生成lst中任取k个元素的组合数
:param lst: 列表
:param k: 选取元素个数
"""
stack = [(i, [lst[i]]) for i in range(len(lst))]
result = []
while stack:
index, comb = stack.pop()
if len(comb) == k:
result.append(comb)
else:
for i in range(index+1, len(lst)):
stack.append((i, comb+[lst[i]]))
return result
# 测试用例
lst = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
k = 3
print(combinations(lst, k))
```
输出:
```
[['A', 'B', 'C'], ['A', 'B', 'D'], ['A', 'B', 'E'], ['A', 'B', 'F'], ['A', 'B', 'G'], ['A', 'B', 'H'], ['A', 'C', 'D'], ['A', 'C', 'E'], ['A', 'C', 'F'], ['A', 'C', 'G'], ['A', 'C', 'H'], ['A', 'D', 'E'], ['A', 'D', 'F'], ['A', 'D', 'G'], ['A', 'D',...
```
相关推荐
![](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)
![](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)