排列组合算法

排列组合算法

paixu

1
2
3
对于abc的排列,当我们进行排列时,可以先考虑第1位可能有哪些情况,如上图所示
有a,b,c三种情况,然后再对后面的两位进行排列,采用相同的思路,可以很容易的
就通过递归实现全排列了。

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def rank(data, step):
"""
:param data:
:param step: 当前的首位
"""
if step == len(data) - 1:
print data
else:
for i in range(step, len(data)):
# 遍历这一层中的各种选择,比如先a首位,然后可选择下一个是b、c
data[step], data[i] = data[i], data[step]
# 递归后面的情况, 选了之后在遍历b、c
rank(data, step + 1)
1
2
3
4
5
有一个数组[1, 2, 3, 4, 5, 6],我想从里面随机选出三个来,有哪些取法。

1,首先从第一个元素下手,对于第一个元素,我们有两个选择:要 or 不要。
2,如果要了,那么我们需要选择的元素就少了一个了,我们只需要从后面的元素中选出两个就够了。
3,如果不要,我们就从第二个元素继续看,此时我们还是要选出三个。

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def combine(data, step, select_data, target_num):
if len(select_data) == target_num:
# 选择的元素已经够了,就输出并返回
print(select_data)
return
if step >= len(data):
# 没有元素选了
return
# 选择当前元素
select_data.append(data[step])
combine(data, step + 1, select_data, target_num)
# 从已选择元素中先删除
select_data.pop()
# 不选择当前元素
combine(data, step + 1, select_data, target_num)