Knuth 演算法如何有效率地產生集合排列？

高效產生集合排列

在產生集合排列的問題中，找到最有效的演算法至關重要。提供的程式碼實現了高效率，但對於要求較高的計算，尋求最佳化。

建議的解決方案：Knuth 演算法

Knuth 演算法提供了一種高效率的排列產生方法。它的操作主要有四個步驟：

1. 辨識最大索引j: 決定目前排列不按升序排列的索引j，其中元素位於索引j 和j 1亂序。
2. 找出下一個較大元素： 決定元素所在的索引l索引j 處的元素小於索引l 處的元素，其中索引j
3. 交換元素： 交換索引j 和l 處的元素。
4. 反轉尾端： 反轉下列元素的順序索引j 1 到

實作

實作

private static bool NextPermutation(int[] numList)
{
  // 1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation.
  var largestIndex = -1;
  for (var i = numList.Length - 2; i >= 0; i--)
  {
    if (numList[i] < numList[i + 1])
    {
      largestIndex = i;
      break;
    }
  }

  // If no such index exists, return false indicating the last permutation.
  if (largestIndex < 0) return false;

  // 2. Find the largest index l such that a[j] < a[l]. Since j + 1 is such an index, l is well defined and satisfies j < l.
  var largestIndex2 = -1;
  for (var i = numList.Length - 1; i >= 0; i--)
  {
    if (numList[largestIndex] < numList[i])
    {
      largestIndex2 = i;
      break;
    }
  }

  // 3. Swap a[j] with a[l].
  var tmp = numList[largestIndex];
  numList[largestIndex] = numList[largestIndex2];
  numList[largestIndex2] = tmp;

  // 4. 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;
}

提供的實作Knuth 演算法的C#程式碼如下：

速度最佳化注意事項

• 為了進一步最佳化速度，請考慮以下：
• 程式碼展開：展開第4 步驟中的反向循環可以稍微提升效能。
• 值快取：快取經常存取的內容值，例如陣列的長度，以最大限度地減少冗餘
• 內聯函數：內聯NextPermutation 函數以消除函數呼叫開銷。

避免不必要的轉換：確保中間值屬於適當的資料型別以避免轉換操作。

以上是Knuth 演算法如何有效率地產生集合排列？的詳細內容。更多資訊請關注PHP中文網其他相關文章！