Python의 내장 함수와 자체 작성 DFS 알고리즘을 사용하여 순열 및 조합 문제를 구현하는 방법

순열 및 조합은 주어진 요소에서 여러 요소를 선택하여 가능한 모든 순열 또는 조합을 찾는 데 사용되는 수학의 일반적인 계산 방법입니다. Python에는 순열 및 조합 계산을 구현하는 방법이 많이 있습니다.

내장 함수 호출

Python 표준 라이브러리는 반복자를 생성하기 위한 많은 도구 함수가 포함된 itertools 모듈을 제공합니다. 그 중 순열과 조합을 계산하는 데 2개의 함수를 사용할 수 있습니다.

- 순열( p [, r]): 시퀀스 p에서 r 요소의 완전한 순열을 꺼내고 이를 결합하여 새 반복자의 요소인 튜플을 얻습니다.
-combinations(p, r): 시퀀스 p에서 r개의 요소를 가져와서 완전한 조합을 형성합니다. 요소는 반복될 수 없습니다. 이 조합은 새 반복자의 요소로 튜플을 생성합니다.

이 두 함수는 모두 반복자 개체를 반환합니다. 이 개체는 list() 함수를 사용하여 목록으로 변환할 수 있거나 해당 요소는 for 루프를 사용하여 탐색할 수 있습니다. 다음은 간단한 예입니다.

1부터 n까지 숫자를 정렬하려면 내장 함수 permutations(iterable,r=None)를 사용하세요.

permutations(iterable,r=None)는 요소에 의해 생성된 길이를 연속적으로 반환합니다. 반복 가능한 시퀀스에서 r의 순열입니다. r이 지정되지 않거나 None인 경우 기본값은 반복 가능한 길이입니다.

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)

작은 수를 열거해야 하는 경우에는 무차별 대입 방식을 직접 사용할 수 있습니다.

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

무차별 대입 방식은 작은 수에 대해 효과적이고 간단합니다.

1부터 n까지의 숫자 조합에는 내장 함수 조합을 사용하세요(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)

자체 작성 알고리즘 DFS 구현

내장 함수를 사용하는 것 외에도 다음과 같이 작성할 수도 있습니다. 순열과 조합을 달성하기 위한 자체 알고리즘이 계산됩니다. 일반적인 알고리즘은 깊이 우선 탐색(DFS)을 사용하여 가능한 모든 상황을 탐색하고 조건을 충족하는 결과를 저장하는 것입니다. 다음은 DFS를 사용하여 완전 순열과 완전 조합을 구현하는 예입니다.

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)

위 코드는 매우 짧지만 한 가지 단점은 작은 것부터 큰 것까지 순열을 출력할 수 없다는 것입니다.

개선된 코드: 작은 것부터 큰 것까지 출력 달성

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)

자체 작성 알고리즘 구현 조합:

# 首先，我们定义一个函数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的方式遍历了它们。

위 내용은 Python의 내장 함수와 자체 작성 DFS 알고리즘을 사용하여 순열 및 조합 문제를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!