c# - 3位数字的递归排列

Question

我正在研究递归查找 3 位数的所有排列。

我厌倦了编写以下排列方法：

    static int a = 1;
    static int b = 2;
    static int c = 3;
    static int aCount;
    static int bCount;
    static int cCount;

    static void perm(int a, int b, int c)
    {

        Console.WriteLine("( {0}, {1}, {2} )", a, b, c); // (1,2,3 )

        if (aCount < 1 && bCount<1 &&cCount<1)
        {
            aCount++;

            perm(a, c, b);
        }
        else
            if (aCount==1 && bCount < 1 && cCount<1)
            {

                bCount++;
                perm(b, a, c);
            }
            else
                if (aCount == 1 && bCount == 1 && cCount < 1)
                 {
                    perm(b,c,a);
                  }
        else
                if (aCount==1 && bCount==1 && cCount < 1)
                {
                    cCount++;
                    perm(c, a, b);  //c b a

                }
               else
                    if (aCount == 1 && bCount == 1 &&  cCount == 1)
                {
                    perm(c, b, a);

                }

            }

我试图涵盖所有案例，每个步骤都有细节，但我仍然突然收到堆栈溢出异常。

我感谢您的贡献，所以感谢转发。

Answer 1

你说你正在尝试递归，但所有这些行都出现在你的代码中：

perm(a, c, b)
perm(b, a, c)
perm(b, c, a)
perm(c, a, b)
perm(c, b, a)

当然还有函数的第一次调用：perm(a, b, c)

这样做要容易得多：

static void perm(int a, int b, int c)
{
    Console.WriteLine("( {0}, {1}, {2} )", a, b, c);
    Console.WriteLine("( {0}, {2}, {1} )", a, b, c);
    Console.WriteLine("( {1}, {0}, {2} )", a, b, c);
    Console.WriteLine("( {1}, {2}, {0} )", a, b, c);
    Console.WriteLine("( {2}, {0}, {1} )", a, b, c);
    Console.WriteLine("( {2}, {1}, {0} )", a, b, c);
}

Answer 2

一方面，这两种情况中的任何一种都会导致无限递归：

if (aCount == 1 && bCount == 1 && cCount < 1)
{
    perm(b,c,a);
}

和：

if (aCount == 1 && bCount == 1 && cCount == 1)
{
    perm(c, b, a);
}

这样做的原因是您没有更改aCount,bCount或cCount, 因此您最终会重复触发相同的案例。

除此之外，您似乎并没有真正递归地考虑问题 - 如另一个答案中所述，所有排列都出现在一个调用中，因此，如果您让它以这种方式工作，您的递归深度将为 2，即然后本质上可能涉及用 print 语句替换每个递归调用，并具有非递归函数。

对于递归解决方案，请尝试考虑在当前调用中处理单个字符并递归到下一个字符的解决方案。

更详细的解释，如果你无法弄清楚：

从第一个字符开始。

尝试将当前字符与每个剩余字符（包括它自己，即什么都不做）交换。

递归到下一个字符。

在最后一个字符处，打印出所有字符。

提示 - 将数组和当前索引传递给您的函数。

Answer 3

我会给你写伪代码：

permutationABC()
{
    int n=3;
    array SOL[n]/* 1 if you get the element  otherwise 0 if you don't get the element , the meaning of SOL is that SOL[0] is 1 if we had got 'a' , otherwise 0. It's the same for the others */
    initSolWithAllZero(SOL)
    permRecursive(abc,SOL,0,n);
}

permRecursive(SOL,i,n)
{
    if i == n then print(SOL) 
    else
    {
        for k=0 to n
        {
             if SOL[k] == 0 then
             {
                  SOL[k]=1 // take 
                  permRecursive(SOL,i+1,n)
                  SOL[K]=0 // don't take ... go back....
             }
        }
    }
}

时间是 O(n*n!) O(n!) 是排列数，O(n) 是打印时间。