堆算法的 C# 实现不起作用

Question

我试图用 C# 编写堆算法的实现，但无法正常工作。我正在尝试创建一个通用实现，它将找到字符串的所有排列，并将它们添加到列表中。

我是这样开始的:

List<string> permutations = new List<string>();
GenerateHeapPermutations(3, "ABC", permutations);

foreach (var p in permutations)
{
    Console.WriteLine(p);
}

Console.ReadKey();

这是我的实现:

public static void GenerateHeapPermutations(int n, string s, List<string> sList)
{
    if (n == 1)
    {
        sList.Add(s);
    }
    else
    {
        for (int i = 0; i < n - 1; i++)
        {
            GenerateHeapPermutations(n - 1, s, sList);

            if (n % 2 == 0)
            {
                // swap the positions of two characters
                var charArray = s.ToCharArray();
                var temp = charArray[i];
                charArray[i] = charArray[n - 1];
                charArray[n - 1] = temp;
                s = new String(charArray);
            }
            else
            {
                var charArray = s.ToCharArray();
                var temp = charArray[0];
                charArray[0] = charArray[n - 1];
                charArray[n - 1] = temp;
                s = new String(charArray);
            }
        }

        GenerateHeapPermutations(n - 1, s, sList);
    }
}

该算法确实产生了正确数量的排列(在本例中为六个)，但排列本身是不正确的:

ABC       BAC       CBA               
BCA       ABC       BAC

我不认为我偏离了 pseudocode example of Heap's algorithm on Wikipedia ，并且由于该算法的递归性质(概念化非常棘手)，我很难对其进行调试。

任何人都可以提供有关问题可能是什么的任何见解吗？

^{附言不是作业，只是为了好玩。}

Answer 1

您的算法基于传递 string 而不是实际数组。 传递 string 时会获取字符串的副本，因此更改复制的字符串不会更改传递的实际字符串。

当把string改成char array时，问题就解决了。

public static void Main()
{
    List<string> permutations = new List<string>();
    GenerateHeapPermutations(3, new [] { 'A', 'B', 'C' }, permutations);

    foreach (var p in permutations)
    {
        Console.WriteLine(p);
    }

    Console.ReadKey();
}

public static void GenerateHeapPermutations(int n, char[] charArray, List<string> sList)
{
    if (n == 1)
    {
        sList.Add(new string(charArray));
    }
    else
    {
        for (int i = 0; i < n - 1; i++)
        {
            GenerateHeapPermutations(n - 1, charArray, sList);

            int indexToSwapWithLast = (n%2 == 0 ? i : 0);
            // swap the positions of two characters
            var temp = charArray[indexToSwapWithLast];
            charArray[indexToSwapWithLast] = charArray[n - 1];
            charArray[n - 1] = temp;
        }

        GenerateHeapPermutations(n - 1, charArray, sList);
    }
}

注意:您可以删除多余的数字n 输入，并使用charArray.Length 从数组长度中导出它但是，我不想不必要地更改您的代码。