C#算法之全排列递归算法实例讲解

什么是全排列？

全排列是指将一个给定的集合中的元素进行排列，使得每个元素只出现一次，且每个元素在排列中的位置是不确定的，从而得到的所有不同排列。比如给定集合{1, 2, 3}的全排列包括{1, 2, 3}、{1, 3, 2}、{2, 1, 3}、{2, 3, 1}、{3, 1, 2}和{3, 2, 1}。

递归算法实现全排列

全排列可以通过递归算法来实现。具体的过程如下：

1. 当集合为空时，递归结束，输出当前排列；

2. 否则，对于给定集合中的每个元素，将它依次与集合中的第一个元素交换位置，然后对剩下的元素进行全排列递归调用。即在每次递归调用中，传入的集合都比上一次递归调用中的集合少了一个元素，直到集合中只有一个元素。

下面是一个基于C#语言实现的全排列递归算法示例：

public static void Permutation(string str, int start, int end)
{
    if(start == end)
    {
        Console.WriteLine(str);
    }
    else
    {
        for(int i = start; i <= end; i++)
        {
            // 将 str[start] 与 str[i] 交换位置
            var tmp = str[start];
            str[start] = str[i];
            str[i] = tmp;

            // 对剩下的部分进行全排列递归调用
            Permutation(str, start + 1, end);

            // 将 str[start] 与 str[i] 交换位置，恢复原有顺序
            tmp = str[start];
            str[start] = str[i];
            str[i] = tmp;
        }
    }
}

其中，参数str表示要进行排列的字符串，参数start表示当前递归调用中待排列部分的起始位置，参数end表示当前递归调用中待排列部分的终止位置。

示例说明

示例1：排列整数数组

假设现在有一个整型数组nums，对于其中的元素进行全排列，可以通过如下代码实现：

var nums = new int[] { 1, 2, 3 };
var str = string.Join("", nums);
Permutation(str.ToCharArray(), 0, str.Length - 1);

输出结果如下：

123
132
213
231
321
312

这里先将数组中的元素连接起来形成一个字符串，再将这个字符串传入全排列函数进行排列。

示例2：排列字符串

假设现在有一个字符串str，对其中的字符进行全排列，可以通过如下代码实现：

var str = "abc";
Permutation(str.ToCharArray(), 0, str.Length - 1);

输出结果如下：

abc
acb
bac
bca
cba
cab

这里直接将字符串转换成字符数组再传入全排列函数进行排列。

注意，由于C#中的字符串是不可变类型，因此在实现全排列算法时需要将字符串转换成可变类型，比如字符数组。