C#实现排列组合算法：递归生成与路径规划应用

算法实现原理

排列与组合的核心区别在于顺序。组合关注的是元素的组成，而排列强调元素的具体顺序。以下算法使用 List<T[]> 作为返回容器，能够处理任意类型的泛型数据：

1. GetCombination (求组合)：通过递归遍历辅助数组下标，按规则选取指定数量的元素，忽略先后顺序，仅保留唯一的数据子集。
2. GetPermutation (求排列)：首先调用 GetCombination 提取出符合条件的元素组，然后针对每个元素组执行内部的全排列，从而得到所有可能的排序结果。

核心代码封装

以下代码实现了核心的递归逻辑，直接复制到项目中即可使用：

public class PermutationAndCombination<T>
 {
 /// <summary>
 /// 交换两个变量
 /// </summary>
 public static void Swap(ref T a, ref T b)
 {
 T temp = a;
 a = b;
 b = temp;
 }

 /// <summary>
 /// 递归算法求数组的组合(私有成员)
 /// </summary>
 private static void GetCombination(ref List<T[]> list, T[] t, int n, int m, int[] b, int M)
 {
 for (int i = n; i >= m; i--)
 {
 b[m - 1] = i - 1;
 if (m > 1)
 {
 GetCombination(ref list, t, i - 1, m - 1, b, M);
 }
 else
 {
 if (list == null) { list = new List<T[]>(); }
 T[] temp = new T[M];
 for (int j = 0; j < b.Length; j++)
 { temp[j] = t[b[j]]; }
 list.Add(temp);
 }
 }
 }

 /// <summary>
 /// 递归算法求排列(私有成员)
 /// </summary>
 private static void GetPermutation(ref List<T[]> list, T[] t, int startIndex, int endIndex)
 {
 if (startIndex == endIndex)
 {
 if (list == null) { list = new List<T[]>(); }
 T[] temp = new T[t.Length];
 t.CopyTo(temp, 0);
 list.Add(temp);
 }
 else
 {
 for (int i = startIndex; i <= endIndex; i++)
 {
 Swap(ref t[startIndex], ref t[i]);
 GetPermutation(ref list, t, startIndex + 1, endIndex);
 Swap(ref t[startIndex], ref t[i]); // 恢复原状以支持下一次循环
 }
 }
 }

 /// <summary>
 /// 求数组中n个元素的组合
 /// </summary>
 public static List<T[]> GetCombination(T[] t, int n)
 {
 if (t.Length < n) return null;
 int[] temp = new int[n];
 List<T[]> list = new List<T[]>();
 GetCombination(ref list, t, t.Length, n, temp, n);
 return list;
 }

 /// <summary>
 /// 求数组中n个元素的排列
 /// </summary>
 public static List<T[]> GetPermutation(T[] t, int n)
 {
 if (n > t.Length) return null;
 List<T[]> list = new List<T[]>();
 List<T[]> c = GetCombination(t, n);
 foreach(var item in c)
 {
 var l = new List<T[]>();
 GetPermutation(ref l, item, 0, n - 1);
 list.AddRange(l);
 }
 return list;
 }
 
 // 其他重载方法保持原有逻辑不变...
 }

具体操作演示

第1步：生成指定数量的组合

若需要从一组数据中提取不重复的子集，可使用以下代码。此处以从数组 { 1, 2, 3, 4, 5 } 中选取 3 个数为例：

static void Main(string[] args)
 {
    int[] IntArr = new int[] { 1, 2, 3, 4, 5 };
    // 获取全部3-3组合
    List<int[]> ListCombination = PermutationAndCombination<int>.GetCombination(IntArr, 3); 
    
    foreach(int[] arr in ListCombination)
    {
        foreach(int item in arr)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine("");
    }
}

运行结果展示了所有不重复的3元组合，输出效果如下：

第2步：生成指定数量的排列

如果需要获取元素的完整顺序组合（即1,2,3 和 3,2,1 视为不同），同样修改调用方法为 GetPermutation：

int[] IntArr = new int[] { 1, 2, 3, 4, 5 }; 
// 获取全部5取3的排列
List<int[]> ListPermutation = PermutationAndCombination<int>.GetPermutation(IntArr, 3);

foreach(int[] arr in ListPermutation)
{
    foreach(int item in arr)
    {
        Console.Write(item + " ");
    }
    Console.WriteLine("");
}

此时控制台输出的行数将明显增加，因为包含了相同元素的不同排序方式：

注意事项与扩展

• 在处理大规模数据时，全排列的复杂度呈指数级增长，建议在实际业务（如路径规划）中结合剪枝策略控制搜索空间。
• 上述代码中的内部参数 t 在递归交换时会发生变异，因此在外部迭代时，如果后续代码仍需依赖原数组的顺序，请在复制后进行操作。

以上就是C#实现排列组合的详细方法，更多关于.NET算法优化的资料请关注本站其它相关文章！