So implementieren Sie Permutations- und Kombinationsprobleme mithilfe der in Python integrierten Funktionen und des selbstgeschriebenen DFS-Algorithmus

Permutation und Kombination ist eine gängige Berechnungsmethode in der Mathematik, die verwendet wird, um alle möglichen Permutationen oder Kombinationen durch Auswahl mehrerer Elemente aus gegebenen Elementen zu finden. In Python gibt es viele Möglichkeiten, Permutations- und Kombinationsberechnungen zu implementieren.

Eingebaute Funktionen aufrufen

Die Python-Standardbibliothek stellt ein Modul itertools bereit, das viele Werkzeugfunktionen zum Generieren von Iteratoren enthält. Darunter können zwei Funktionen zum Berechnen von Permutationen und Kombinationen verwendet werden, nämlich:

- Permutationen( p [, r]): Nehmen Sie die vollständige Permutation von r Elementen aus der Sequenz p heraus und kombinieren Sie sie, um das Tupel als Element des neuen Iterators zu erhalten.
-combinations(p, r): Nimm r Elemente aus der Sequenz p, um eine vollständige Kombination zu bilden. Die Elemente dürfen nicht wiederholt werden. Die Kombination ergibt ein Tupel als Element des neuen Iterators.

Diese beiden Funktionen geben ein Iteratorobjekt zurück, das mit der Funktion list() in eine Liste konvertiert werden kann, oder dessen Elemente mit einer for-Schleife durchlaufen werden können. Das Folgende ist ein einfaches Beispiel:

Um Zahlen von 1 bis n anzuordnen, verwenden Sie die integrierte Funktion permutations(iterable,r=None);

permutations(iterable,r=None) gibt kontinuierlich die von den Elementen generierte Länge zurück in der iterierbaren Sequenz Ist die Permutation von r. Wenn r nicht angegeben ist oder Keine ist, ist der Standardwert die Länge der iterierbaren Sequenz.

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)

Wenn Sie eine kleine Zahl aufzählen müssen, können Sie direkt die Brute-Force-Methode verwenden

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

Die Brute-Force-Methode ist effektiv und einfach für kleine Zahlen.

Für Kombinationen von 1 bis n Zahlen verwenden Sie die integrierten Funktionskombinationen (iterierbar, r=Keine)

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)

Selbstgeschriebene Algorithmus-DFS-Implementierung

Zusätzlich zur Verwendung integrierter Funktionen können wir auch unsere schreiben Eigene Algorithmen zur Erzielung von Permutationen und Kombinationen berechnen. Ein gängiger Algorithmus besteht darin, die Tiefensuche (DFS) zu verwenden, um alle möglichen Situationen zu durchsuchen und die Ergebnisse zu speichern, die die Bedingungen erfüllen. Das Folgende ist ein Beispiel für die Verwendung von DFS, um eine vollständige Permutation und vollständige Kombination zu erreichen:

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)

Obwohl der obige Code sehr kurz ist, besteht ein Nachteil darin, dass er die Permutation von klein nach groß nicht ausgeben kann.

Verbesserter Code: Erzielen Sie eine Ausgabe von klein bis groß

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)

Selbst geschriebene Algorithmus-Implementierungskombination:

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

Das obige ist der detaillierte Inhalt vonSo implementieren Sie Permutations- und Kombinationsprobleme mithilfe der in Python integrierten Funktionen und des selbstgeschriebenen DFS-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!