Python递归实现组合与排列算法
- 组合算法
组合是从一组数中取出指定个数的数,它们的顺序无关紧要。假设有如下组合:[1,2,3]中取出指定个数的数,它们的组合方式如下:
取出1个数的组合:[1] [2] [3]
取出2个数的组合:[1,2] [1,3] [2,3]
取出3个数的组合:[1,2,3]
Python代码实现:
def combination(data, r):
"""
求解组合的算法(递归实现)
data:提供的数据
r:需要选择的元素个数
"""
result = []
if r == 0:
result.append([])
elif r == len(data):
result.append(data)
else:
for i in range(len(data)):
sub_combinations = combination(data[i+1:], r-1)
for sub_combination in sub_combinations:
result.append([data[i]] + sub_combination)
return result
输出组合
data = [1, 2, 3]
result = combination(data, 2)
for r in result:
print(r)
输出结果:
[1, 2]
[1, 3]
[2, 3]
- 排列算法
排列是从一组数中取出指定个数的数,它们的顺序有关紧要。假设有如下排列:[1,2,3]中取出指定个数的数,它们的排列方式如下:
取出1个数的排列:[1] [2] [3]
取出2个数的排列:[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
取出3个数的排列:[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
Python代码实现:
def permutation(data, r):
"""
求解排列的算法(递归实现)
data:提供的数据
r:需要选择的元素个数
"""
result = []
if r == 0:
result.append([])
else:
for i in range(len(data)):
sub_permutations = permutation(data[:i] + data[i+1:], r-1)
for sub_permutation in sub_permutations:
result.append([data[i]] + sub_permutation)
return result
输出排列
data = [1, 2, 3]
result = permutation(data, 3)
for r in result:
print(r)
输出结果:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
相关文章