最佳化排列產生演算法
高效率地產生集合的排列是電腦科學中的經典問題。雖然提供的程式碼很高效,但對於較大的集合,它可能仍然需要大量時間。
可以透過使用 Knuth 演算法進行一項改進,該演算法的時間複雜度為 O(n),其中 n 的大小該集。這是基於 Knuth 演算法的修訂版本:
public static bool NextPermutation(int[] numList) { // Find the largest index j such that a[j] < a[j + 1] var largestIndex = -1; for (var i = numList.Length - 2; i >= 0; i--) { if (numList[i] < numList[i + 1]) { largestIndex = i; break; } } // If there's no such index, we have reached the last permutation if (largestIndex < 0) return false; // Find the largest index l such that a[j] < a[l] var largestIndex2 = -1; for (var i = numList.Length - 1; i >= 0; i--) { if (numList[largestIndex] < numList[i]) { largestIndex2 = i; break; } } // Swap a[j] with a[l] var tmp = numList[largestIndex]; numList[largestIndex] = numList[largestIndex2]; numList[largestIndex2] = tmp; // Reverse the sequence from a[j + 1] up to and including the final element a[n] for (int i = largestIndex + 1, j = numList.Length - 1; i < j; i++, j--) { tmp = numList[i]; numList[i] = numList[j]; numList[j] = tmp; } return true; }
此最佳化演算法使用更有效的方式按升序找出下一個排列。它通常更快,特別是對於較大的集合。但是,為了獲得更高的效率,請考慮使用專為高效排列生成而設計的語言或函式庫。
以上是我們如何針對更大的資料集優化排列生成演算法?的詳細內容。更多資訊請關注PHP中文網其他相關文章!