算法

分治算法

在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范型。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

代码示例

列出 1-5【任意不依次】取 3 个【可重复】的各种可能性 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def divide_and_conquer(nums, length):
    if length == 1:
        return [[num] for num in nums]
    
    smaller_combinations = divide_and_conquer(nums, length - 1)
    all_combinations = []
    
    for combination in smaller_combinations:
        for num in nums:
            all_combinations.append(combination + [num])
    
    return all_combinations

numbers = [1, 2, 3, 4, 5]
combination_length = 3
combinations = divide_and_conquer(numbers, combination_length)

for combination in combinations:
    print(combination)

列出 1-5【任意不依次】取 3 个【不重复】的各种可能性 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

def divide_and_conquer(nums, length):
    if length == 1:
        return [[num] for num in nums]
    
    smaller_combinations = divide_and_conquer(nums, length - 1)
    all_combinations = []
    
    for combination in smaller_combinations:
        for num in nums:
            if num not in combination:
                all_combinations.append(combination + [num])
    
    return all_combinations

def generate_combinations(nums, length):
    if length == 0:
        return [[]]
    
    if not nums:
        return []
    
    current_num = nums[0]
    remaining_nums = nums[1:]
    
    with_current = [[current_num] + combination for combination in generate_combinations(remaining_nums, length - 1)]
    without_current = generate_combinations(remaining_nums, length)
    
    return with_current + without_current

# Define the range of numbers and the length of combinations
numbers = [1, 2, 3, 4, 5]
combination_length = 3

# Generate all possible combinations
combinations = generate_combinations(numbers, combination_length)

# Print each combination
for combination in combinations:
    print(combination)

列出 1-5【依次】取 3 个【可重复】的各种可能性 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def divide_and_conquer(nums, length):
    if length == 1:
        return [[num] for num in nums]
    
    smaller_combinations = divide_and_conquer(nums, length - 1)
    all_combinations = []
    
    for combination in smaller_combinations:
        for num in nums:
            all_combinations.append(combination + [num])
    
    return all_combinations

numbers = [1, 2, 3, 4, 5]
combination_length = 3
combinations = divide_and_conquer(numbers, combination_length)

for combination in combinations:
    print(combination)

列出 1-5【依次】取 3 个【不重复】的各种可能性 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def divide_and_conquer(nums, length):
    if length == 1:
        return [[num] for num in nums]
    
    all_combinations = []
    for i in range(len(nums)):
        num = nums[i]
        remaining_nums = nums[i+1:]
        smaller_combinations = divide_and_conquer(remaining_nums, length - 1)
        for combination in smaller_combinations:
            all_combinations.append([num] + combination)
    
    return all_combinations

numbers = [1, 2, 3, 4, 5]
combination_length = 3
combinations = divide_and_conquer(numbers, combination_length)

for combination in combinations:
    print(combination)