使用 Heap’s Algorithm 在 C# 中高效生成排列
在很多需要處理全排列的場景下，Heap’s Algorithm 以其簡潔和高效的特點受到廣泛關注。它通過最少的交換操作，就可以遞歸地生成給定序列的所有排列。本文將詳細介紹這一算法的原理，給出 C# 實現，并展示一個簡單的調度示例，讓你快速上手并運用到實際項目中。
認識 Heap’s Algorithm
Heap’s Algorithm 最早由 B. R. Heap 提出，用于在 O(n!) 的時間復雜度內生成 n 個元素的所有排列。它通過一系列遞歸調用和交換操作，不斷產生新的排列結果。算法的兩個核心思想是：
- 最小交換：僅在需要生成新的排列時交換元素，最大程度減少不必要的操作。
- 遞歸生成：通過對子序列做遞歸處理，再配合交換操作，形成完整的排列。
算法原理簡述
對一個含有 n 個元素的序列進行全排列時，可以分為以下幾個步驟：
- 如果 n = 1，序列本身就是唯一排列，輸出結果即可。
- 循環 n 次：
遞歸生成前 n-1 個元素的所有排列。
依據當前循環次數，決定交換對象（對于奇數次數，交換第 0 個元素與第 n-1 個元素；對于偶數次數，交換當前循環次數對應的元素與第 n-1 個元素）。
在多次迭代和交換后，會依次生成所有排列。
C# 實現示例
下面的代碼展示了一個使用 Heap’s Algorithm 生成任意數組所有排列的示例。示例中，為了演示方便，我們使用了一個簡單的 char 數組作為測試對象。
using System;
using System.Collections.Generic;
public class HeapsAlgorithmExample
{
public static void Main()
{
// 測試數組，可自由修改內容進行測試
char[] tasks = { 'A', 'B', 'C' };
// 存儲所有排列結果
List<string> results = GeneratePermutations(tasks);
// 輸出所有結果
Console.WriteLine("所有排列結果：");
foreach (var permutation in results)
{
Console.WriteLine(permutation);
}
}
/// <summary>
/// 生成指定數組所有排列并返回字符串形式
/// </summary>
/// <param name="array">需要排列的字符數組</param>
/// <returns>所有排列的列表</returns>
public static List<string> GeneratePermutations(char[] array)
{
List<string> permutations = new List<string>();
GeneratePermutations(array, array.Length, permutations);
return permutations;
}
/// <summary>
/// Heap's Algorithm 遞歸函數
/// </summary>
/// <param name="array">需要排列的字符數組</param>
/// <param name="size">當前處理中所使用的數字長度</param>
/// <param name="results">用來保存排列結果的列表</param>
private static void GeneratePermutations(char[] array, int size, List<string> results)
{
// 若當前處理長度為1，說明已經固定了前面所有元素
if (size == 1)
{
// 將當前數組轉換為字符串加入結果
results.Add(new string(array));
return;
}
// 繼續生成長度 size - 1 的所有排列
for (int i = 0; i < size; i++)
{
GeneratePermutations(array, size - 1, results);
// 根據當前層級是奇數還是偶數決定如何交換
if (size % 2 == 1)
{
// 奇數層，交換第0個元素和第 size-1 個元素
Swap(array, 0, size - 1);
}
else
{
// 偶數層，交換第 i 個元素和第 size-1 個元素
Swap(array, i, size - 1);
}
}
}
/// <summary>
/// 交換數組中兩個元素
/// </summary>
private static void Swap(char[] array, int indexA, int indexB)
{
char temp = array[indexA];
array[indexA] = array[indexB];
array[indexB] = temp;
}
}運行輸出示例
以輸入 {'A', 'B', 'C'} 為例，可能的輸出排列包括：
圖片
（不同的初始交換策略可能導致順序稍有不同，但最終生成的排列集一致。）
Linq示例
namespace AppHeap
{
// 擴展方法：生成排列
public static class EnumerableExtensions
{
public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> source)
{
return source.Permutations(source.Count());
}
public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> source, int count)
{
if (count > source.Count())
throw new ArgumentException("Count cannot be greater than source size.");
return PermutationsImpl(source, count);
}
private static IEnumerable<IEnumerable<T>> PermutationsImpl<T>(IEnumerable<T> source, int count)
{
if (count == 0)
yield return Enumerable.Empty<T>();
else
{
int index = 0;
foreach (T element in source)
{
var remainingItems = source.Where((e, i) => i != index);
foreach (var permutation in PermutationsImpl(remainingItems, count - 1))
{
yield return permutation.Prepend(element);
}
index++;
}
}
}
}
internal class Program
{
public static void Main()
{
char[] tasks = { 'A', 'B', 'C' };
var uniqueCombinations = tasks
.Permutations()
.Select(p => new string(p.ToArray()));
foreach (var combination in uniqueCombinations)
{
Console.WriteLine(combination);
}
Console.WriteLine($"\n總組合數：{uniqueCombinations.Count()}");
}
}
}
圖片
應用示例：簡單調度問題
在實際場景中，常常需要考量任務的不同執行順序。例如，有一組任務 {A, B, C}，我們想知道所有可能的完成順序，以幫助評估時間、資源或依賴關系。使用上述方法，我們就能將所有可能的執行順序一并羅列出來，進而對每一種情況進行分析——例如，統計在不同順序下完成任務的總耗時、判斷是否有資源沖突等。
對于更復雜的調度需求，如任務間存在優先級或依賴關系，可以在生成排列后再進行過濾或排序，以排除不滿足約束的情形，或根據自定義規則從所有排列中選取最優方案。
結語
Heap’s Algorithm 通過最少的交換次數，在 O(n!) 的時間內生成 n 個元素的所有排列，適用于各種需要遍歷所有順序的場景。無論是基礎學習、學術研究，還是需要枚舉方案的生產環境，這一算法都是簡單且高效的工具。希望通過本文的示例，你能對 Heap’s Algorithm 的核心思想和 C# 實現方式有更加直觀的認識，并能夠根據自己的業務需求進行擴展和應用。
