Bagaimana untuk melaksanakan masalah pilih atur dan gabungan menggunakan fungsi terbina dalam Python dan algoritma DFS yang ditulis sendiri

Permutasi dan gabungan ialah kaedah pengiraan biasa dalam matematik, yang digunakan untuk mencari semua pilih atur atau gabungan yang mungkin untuk memilih beberapa elemen daripada elemen yang diberikan. Dalam Python, terdapat banyak cara untuk melaksanakan pengiraan pilih atur dan gabungan.

Memanggil fungsi terbina dalam

Pustaka standard Python menyediakan modul itertools, yang mengandungi banyak fungsi alat untuk menjana iterator, yang mana 2 fungsi boleh digunakan Untuk mengira pilih atur dan gabungan , ia adalah:

- pilih atur(p [, r]): Keluarkan pilih atur lengkap elemen r daripada jujukan p, dan gabungkan untuk mendapatkan tupel sebagai elemen lelaran baharu .
- kombinasi(p, r): Ambil r elemen daripada jujukan p untuk membentuk gabungan penuh elemen berulang tidak dibenarkan.

Kedua-dua fungsi ini mengembalikan objek iterator, yang boleh ditukar kepada senarai menggunakan fungsi list() atau elemennya boleh dilalui menggunakan gelung for. Berikut ialah contoh mudah:

Untuk menyusun nombor daripada 1 hingga n, gunakan pilih atur fungsi terbina dalam(iterable,r=None); kembali secara berterusan Unsur-unsur dalam jujukan boleh lelar menjana pilihatur panjang r Jika r tidak dinyatakan atau Tiada, nilai lalai ialah panjang lelaran.

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)

Jika anda perlu menghitung nombor yang kecil, anda boleh terus menggunakan kaedah brute force

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

Kaedah brute force berkesan dan mudah untuk nombor kecil.

Untuk gabungan 1 hingga n nombor, gunakan gabungan fungsi terbina dalam(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)

Pelaksanaan DFS algoritma tulisan sendiri

Selain menggunakan terbina dalam Selain fungsi, kami juga boleh menulis algoritma kami sendiri untuk melaksanakan pengiraan pilih atur dan gabungan. Algoritma biasa ialah menggunakan carian mendalam-pertama (DFS) untuk merentasi semua situasi yang mungkin dan menyimpan hasil yang memenuhi syarat. Berikut ialah contoh penggunaan DFS untuk mencapai pilih atur penuh dan gabungan penuh:

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)

Walaupun kod di atas sangat pendek, satu kelemahan ialah ia tidak boleh mengeluarkan pilih atur daripada kecil ke besar.

Kod yang dipertingkatkan: merealisasikan output daripada kecil kepada besar

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)

Gabungan pelaksanaan algoritma tulisan sendiri:

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

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan masalah pilih atur dan gabungan menggunakan fungsi terbina dalam Python dan algoritma DFS yang ditulis sendiri. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!