How to implement permutation and combination problems using Python's built-in functions and self-written DFS algorithm

Permutation and combination is a common calculation method in mathematics, which is used to find all possible permutations or combinations of selecting several elements from given elements. In Python, there are many ways to implement permutation and combination calculations.

Calling built-in functions

The Python standard library provides a module itertools, which contains many tool functions for generating iterators, of which 2 functions can be used For calculating permutations and combinations, they are:

- permutations(p [, r]): Take out the complete permutation of r elements from the sequence p, and combine to obtain the tuple as the element of the new iterator .
- combinations(p, r): Take r elements from the sequence p to form a complete combination. Repeated elements are not allowed. The combination results in a tuple as the element of the new iterator.

Both these two functions return an iterator object, which can be converted to a list using the list() function, or its elements can be traversed using a for loop. The following is a simple example:

To arrange numbers from 1 to n, use the built-in function permutations(iterable,r=None);

permutations(iterable,r=None) returns continuously The elements in the iterable sequence generate a permutation of length r. If r is not specified or is None, the default value is the length of the iterable.

from itertools import *
s = [1,2,3,4,5]
for element in permutations(s,2):
    a = "".join(str(element))
    print(a,end="")
out[1]:(1, 2)(1, 3)(1, 4)(1, 5)(2, 1)(2, 3)(2, 4)(2, 5)(3, 1)(3, 2)(3, 4)(3, 5)(4, 1)(4, 2)(4, 3)(4, 5)(5, 1)(5, 2)(5, 3)(5, 4)

If you need to enumerate a small number, you can directly use the brute force method

for i in range(5):
    for j in range(5):
        if i!=j:
            print(s[i],s[j])

The brute force method is effective and simple for small numbers.

For combinations of 1 to n numbers, use the built-in function combinations(iterable,r=None)

In [30]: from itertools import *
s = {1,2,3,4}
for element in combinations(s,3):
    a = "".join(str(element))
    print(a,end="")
(1, 2, 3)(1, 2, 4)(1, 3, 4)(2, 3, 4)

Self-written algorithm DFS implementation

In addition to using the built-in In addition to functions, we can also write our own algorithms to implement calculations of permutations and combinations. A common algorithm is to use depth-first search (DFS) to traverse all possible situations and save the results that meet the conditions. The following is an example of using DFS to achieve full permutation and full combination:

a = [1,2,3,4,5]
def dfs(s,t):
    if s==2: 
        for i in range(0,2):
            print(a[i],end="")
        print(" ")
        return
    for i in range(s,t+1):
        a[s],a[i] = a[i],a[s]
        dfs(s+1,t)
        a[s],a[i] = a[i],a[s]
dfs(0,4)

Although the above code is very short, one disadvantage is that it cannot output the permutation from small to large.

Improved code: realize output from small to large

a = [1,2,3,4,5]
b = [0] * 10
vis = [0] * 20
def dfs(s,t):
    if s==2:
        for i in range(0,2):
            print(b[i],end="")
        print(" ")
        return 
    for i in range(0,t):
        if not vis[i]:
            vis[i] = True
            b[s] = a[i]
            dfs(s+1,t)
            vis[i] = False
dfs(0,5)

Self-written algorithm implementation combination:

# 首先，我们定义一个函数dfs，它接受五个参数：
# - cur: 当前遍历到的元素的下标，初始为0
# - m: 要选出的元素个数
# - cur_list: 保存当前已选出的元素的列表
# - original_list: 给定的n个元素的列表
# - result_list: 保存最终结果的列表
def dfs(cur, m, cur_list, original_list, result_list):
    # 如果已经选出了m个元素，就把当前列表添加到结果列表中，并返回
    if m == 0:
        result_list.append(list(cur_list))
        return
    # 如果还没有选出m个元素，就从当前下标开始，遍历原始列表中的每个元素
    for i in range(cur, len(original_list)):
        # 把当前元素添加到当前列表中
        cur_list.append(original_list[i])
        # 递归地调用dfs函数，更新下标和剩余元素个数
        dfs(i + 1, m - 1, cur_list, original_list, result_list)
        # 回溯时，把当前元素从当前列表中移除
        cur_list.pop()
# 然后，我们定义一个测试函数，给定一个原始列表和一个目标个数，调用dfs函数，并打印结果列表
def test(original_list, m):
    # 初始化结果列表为空列表
    result_list = []
    # 调用dfs函数，传入初始下标为0，空的当前列表和结果列表
    dfs(0, m, [], original_list, result_list)
    # 打印结果列表
    print(result_list)
# 最后，我们用一个例子来测试一下我们的算法，假设原始列表为[1, 2, 3, 4]，目标个数为2
test([1, 2, 3, 4], 3)
# 输出结果为：
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
# 可以看到，我们的算法成功地找到了所有的组合，并用DFS的方式遍历了它们。

The above is the detailed content of How to implement permutation and combination problems using Python's built-in functions and self-written DFS algorithm. For more information, please follow other related articles on the PHP Chinese website!