Python の組み込み関数と自作の DFS アルゴリズムを使用して順列と組み合わせの問題を実装する方法

順列と組み合わせは数学における一般的な計算方法であり、指定された要素から複数の要素を選択する際に考えられるすべての順列または組み合わせを見つけるために使用されます。 Python では、順列計算と組み合わせ計算を実装する方法がたくさんあります。

組み込み関数の呼び出し

Python 標準ライブラリには、反復子を生成するための多くのツール関数が含まれるモジュール itertools が用意されており、そのうちの 2 つの関数は順列と組み合わせの計算に使用できます。

- permutations(p [, r]): シーケンス p から r 要素の完全な順列を取り出し、結合して新しい反復子の要素としてタプルを取得します。
-combinations(p, r): シーケンス p から r 要素を取り出して、完全な組み合わせを形成します。要素の繰り返しは許可されません。組み合わせの結果、新しい反復子の要素としてタプルが生成されます。

これら 2 つの関数はどちらもイテレータ オブジェクトを返します。このオブジェクトは 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)

上記のコードは非常に短いですが、欠点の 1 つは、小さい順から大きい順への順列を出力できないことです。

コードの改善: 小規模から大規模までの出力を実現

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 中国語 Web サイトの他の関連記事を参照してください。