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