Comment implémenter des problèmes de permutation et de combinaison à l'aide des fonctions intégrées de Python et de l'algorithme DFS auto-écrit

La permutation et la combinaison sont une méthode de calcul courante en mathématiques, qui est utilisée pour trouver toutes les permutations ou combinaisons possibles en sélectionnant plusieurs éléments parmi des éléments donnés. En Python, il existe de nombreuses façons d’implémenter des calculs de permutation et de combinaison.

Appel de fonctions intégrées

La bibliothèque standard Python fournit un module itertools, qui contient de nombreuses fonctions outils pour générer des itérateurs, dont 2 fonctions peuvent être utilisées pour calculer les permutations et les combinaisons, à savoir :

- permutations(p [, r]) : prendre la permutation complète de r éléments de la séquence p et la combiner pour obtenir des tuples comme éléments de le nouvel itérateur.
- combinaisons(p, r) : prenez r éléments de la séquence p pour former une combinaison complète. Les éléments ne peuvent pas être répétés. La combinaison donne lieu à un tuple comme élément du nouvel itérateur.

Ces deux fonctions renvoient un objet itérateur, qui peut être converti en liste à l'aide de la fonction list(), ou ses éléments peuvent être parcourus à l'aide d'une boucle for. Voici un exemple simple :

Pour organiser les nombres de 1 à n, utilisez la fonction intégrée permutations(iterable,r=None); r= Aucun) Renvoie en continu une permutation de longueur r générée par les éléments de la séquence itérable. Si r n'est pas spécifié ou est Aucun, la valeur par défaut est la longueur de l'itérable.

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)

Si vous avez besoin d'énumérer un petit nombre, vous pouvez directement utiliser la méthode de la force brute

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

La méthode de la force brute est efficace et simple pour les petits nombres.

Pour les combinaisons de nombres de 1 à n, utilisez les combinaisons de fonctions intégrées (itérable,r=Aucun)

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)

Implémentation DFS d'algorithme auto-écrit

# 🎜🎜#

En plus d'utiliser des fonctions intégrées, nous pouvons également écrire nos propres algorithmes pour mettre en œuvre des calculs de permutation et de combinaison. Un algorithme courant consiste à utiliser la recherche en profondeur d'abord (DFS) pour parcourir toutes les situations possibles et enregistrer les résultats qui remplissent les conditions. Ce qui suit est un exemple d'utilisation de DFS pour obtenir une permutation complète et une combinaison complète :

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)

Bien que le code ci-dessus soit très court, un inconvénient est qu'il ne peut pas afficher la permutation de petit à grand. .

Code amélioré : réalisez des résultats de petit à grand

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)

Combinaison d'implémentation d'algorithmes auto-écrits :

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!