排列組合是數學中的一種常見的計算方法,用於求出從給定的元素中選取若干個元素的所有可能的排列或組合。在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) 連續返回iterable序列中的元素產生的長度為r的排列,如果r未指定或為None,則預設值為iterable的長度。
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個數字進行組合,使用內建函數combinations(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實現全排列與全組合的範例:上述程式碼雖然很短,但有個缺點就是無法從小到大輸出排列。 改進之後的程式碼:實作從小到大輸出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中文網其他相關文章!