給定一個由不同元素組成的數組,目標是列出數組元素的所有可能排列。
以下演算法在O(N!) 時間內產生所有排列複雜度:
def permute(arr, i=0): if i == len(arr) - 1: print(arr) return for j in range(i, len(arr)): arr[i], arr[j] = arr[j], arr[i] permute(arr, i + 1) arr[i], arr[j] = arr[j], arr[i]迭代數組:
當i 小於數組長度時:
def permute_repeated(arr): ind = [0] * len(arr) for i in range(len(arr)): ind[i] = i while True: yield [arr[i] for i in ind] for i in range(len(arr) - 2, -1, -1): if ind[i] < ind[i + 1]: break if i == -1: return for j in range(len(arr) - 1, -1, -1): if arr[j] > arr[i]: ind[i], ind[j] = ind[j], ind[i] break ind[i + 1:] = sorted(ind[i + 1:])當: 未完成時: 找出主元:找出元素小於其的最大索引後繼者。 找出相鄰: 找出排序部分中大於樞軸索引處的元素的最後一個元素。 交換:交換樞軸和相鄰索引處的元素。 反轉:反轉從樞軸索引到排序部分末端的元素。 檢查完成:檢查陣列是否依降序排序。如果是,則退出循環。 Python 實作
以上是如何產生數組的所有排列,包括具有重複元素的排列?的詳細內容。更多資訊請關注PHP中文網其他相關文章!