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을 변경하지 않는 당신이 반복적으로 같은 사건을 유발하게 될 겁니다 있도록한다는 것입니다.

너는 재귀 적으로 문제를 재귀 적으로 생각하는 것 같지 않습니다 - 다른 대답에서 언급했듯이, 모든 순열은 한 번의 호출로 나타납니다. 그렇게한다면, 당신의 재귀 깊이 will 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.... 
      } 
     } 
    } 
} 

시간은 (! n)이 순열과 O (N)의 수입니다 O (! n 개의 * n)도 O입니다을 인쇄 시간입니다.