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

Question

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

我是这样开始的:

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);
    }
}

该算法确实产生了正确的排列数(在这种情况下为6),但排列本身是不正确的:

ABC       BAC       CBA               
BCA       ABC       BAC

我不认为我偏离了维基百科上Heap算法的伪代码示例,而且由于这种算法的递归特性,我很难调试这个算法(概念化非常棘手).

谁能提供任何有关问题的见解？

^{PS不是作业,只是为了好玩.}

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但是,我不想不必要地更改您的代码.

Answer 2

首先要做的事情是：调试。处理递归时，调试代码的最简单方法是在 IDE 中设置断点并逐步执行它，并记录代码的行为是否符合您的预期。这使您可以在每一步查看变量的值。

您会发现在任何地方传递字符串都不会产生您期望的结果，因为您传递的是它的副本而不是实际值。如果您改为通过引用传递（不确定 C# 是否允许），您将执行您所期望的操作。