排列组合算法

Posted on Edited on

排列组合算法

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)