使用 Knuth 演算法快速產生排列
最佳化排列的產生是電腦科學中的基本問題。這在處理大型資料集時尤其重要,因為列舉所有排列所需的時間可能會變得很長。以下程式碼片段展示了一種用於產生排列的高效演算法,稱為Knuth 演算法:
private static bool NextPermutation(int[] numList) { // Find the largest index j such that a[j] < a[j + 1]. int largestIndex = -1; for (int i = numList.Length - 2; i >= 0; i--) { if (numList[i] < numList[i + 1]) { largestIndex = i; break; } } // If no such index exists, the permutation is the last permutation. if (largestIndex < 0) return false; // Find the largest index l such that a[j] < a[l]. int largestIndex2 = -1; for (int i = numList.Length - 1 ; i >= 0; i--) { if (numList[largestIndex] < numList[i]) { largestIndex2 = i; break; } } // Swap a[j] with a[l]. int 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; }
該演算法的運行時間為O(n^2),其中n 表示輸入清單中的元素數量。它採用多種最佳化來最小化計算,包括:
這些最佳化確保了集合中下一個排列的高效生成,使得該演算法非常適合需要快速排列的應用世代。
以上是Knuth 演算法如何有效率地生成排列?的詳細內容。更多資訊請關注PHP中文網其他相關文章!