'팩토리얼'에 해당되는 글 1건

  1. 2008.03.18 non-recursive 한 permutation 구현하기

자료구조 과제..

이거... 알고리즘 보고 옮기긴 했지만... 이해하기 어렵다;

/************************************************************************/
/* 과목명 : Data structure            */
/* 교수님 : 유 하 진 교수님            */
/* 파일명 : Perm_hw.cpp                                                 */
/* 작성일 : 2008. 03. 18.            */
/* 작성자 : 박상현              */
/* 내 용  : recursive 하지 않은 permutation 을 구현한다.    */
/************************************************************************/

/*
 * Declare headers
 */
#include <stdio.h>
#include <string.h>
#include <malloc.h>

/*
 * Declare functions
 */
void init(int*, int, int);      //  각 variable 들을 초기화한다.
int factorial(int);        // 팩토리얼 함수
int numLeft;         // 남아있는 순열의 개수를 표시한다.
int* getNext(int*, int, int);     //

/************************************************************************/
/* 함수명 : main                                                        */
/* permutation 을 적용시킬 문자열을 입력받고, 문자열의 길이를 구해서    */
/* 순열을 만들어낸다.             */
/************************************************************************/
int main(char *argv[], int argc)
{
 int *indexes, *indexList;  // 인덱스의 순서를 가지는 배열 ( indexes = indexList )
 char *buf;      // 문자열을 담아둘 버퍼
 char elements[255];    // 입력받는 문자열의 저장소
 int total;      // 순열의 총 개수
 int i, len, cnt = 0;   // 문자열의 길이와 카운터

 printf("문자열을 입력하세요 : ");
 scanf("%s", elements);         // 문자열을 입력받는다.
 len = strlen(elements);         // 문자열의 길이를 구한다.
 total = factorial(len);         // 순열의 개수를 팩토리얼로 구한다.
 buf = (char *)malloc(sizeof(char) * len);    // 버퍼에 메모리를 할당한다.
 indexList = (int *)malloc(sizeof(int) * len);   // 인덱스 리스트에 메모리를 할당한다.
 init(indexList, len, total);       // 리스트를 초기화한다.
 
 
 // 남아있는 순열의 개수가 0 보다 클동안 loop
 while(numLeft > 0)
 {
  indexes = getNext(indexList, len, total);   // indexList 를 리턴받는다.
  for(i = 0 ; i < len ; i++)
  {
   buf[i] = elements[indexes[i]];     // indexes 의 순서대로 버퍼에 저장한다.
  }
  for(i = 0 ; i < len ; i++)
  {
   printf("%c", buf[i]);       // 버퍼의 내용을 출력한다.
  }
  printf("\t");

  cnt++;
 }
 printf("\n순열의 총 개수 = %d\n", cnt);
 
 
 
 return 0;
}

/************************************************************************/
/* 함수명 : getNext                                                     */
/* 실질적으로 순열을 만들어내는 함수이다.        */
/* 1. 먼저 입력받은 문자열을 한번 그대로 출력한다.      */
/* 2. j + 1 로 가장 큰 인덱스를 가리키는 j 를 찾아낸다.     */
/* 3. indexList[j] 보다 큰 가장 작은 인덱스를 가리키는 k 를 찾는다.  */
/* 4. j 와 k 를 SWAP 한다.            */
/* 5. r 을 마지막 인덱스, s 를 j + 1 로 둔다.       */
/* 6. r 이 s 보다 클동안 indexList[r] 과 indexList[s] 를 SWAP 하며 r */
/*    은 증가시키고 s 는 감소시킨다.         */
/************************************************************************/
int* getNext(int *indexList, int n, int total)
{
 int j, k, r, s;
 int temp;

 
 // 일단 입력받는 문자열을 그대로 한번 출력 ( numLeft == total )
 if(numLeft == total)
 {
  numLeft -= 1;
  return indexList;
 }

 // Find largest index j with a[j] < a[j+1]
 j = n - 2; // 끝에서 두번째 인덱스
 // 마지막 인덱스 두개를 비교해서 왼쪽 것이 더 클동안 왼쪽으로 한칸씩 시프트한다.
 // j 는 1 씩 줄여나간다. ( j + 1 이 가장 큰 인덱스가 된다. )
 while (indexList[j] > indexList[j + 1])  
 {
  j--;
 }

 // Find index k such that a[k] is smallest integer
 // greater than a[j] to the right of a[j]
 k = n - 1;
 // 가장 뒤부터 indexList[j] 보다 큰 가장 작은 인덱스를 가리키는 k 를 찾는다.
 while (indexList[j] > indexList[k])
 {
  k--;
 }

 // j 와 k 를 SWAP 한다.
 temp = indexList[k];
 indexList[k] = indexList[j];
 indexList[j] = temp;

  // Put tail end of permutation after jth position in increasing order
  r = n - 1;   // r = 마지막 인덱스
  s = j + 1;   // j 의 오른쪽 인덱스
 
  // r 이 s 보다 클동안 indexList[r] 와 indexList[s] 를 SWAP 한다.
  // r 은 1 씩 감소시키고, s 는 1 씩 증가시킨다.
  while (r > s)
  {
    temp = indexList[s];
    indexList[s] = indexList[r];
    indexList[r] = temp;
    r--;
    s++;
 }
 numLeft -= 1;  // 남아있는 순열의 개수가 하나 줄어든다.
 return indexList; // 결과 인덱스리스트를 리턴한다.
}

/************************************************************************/
/* 함수명 : init                                                        */
/* 문자열 : 길이가 n 인 문자열의 인덱스 리스트를 초기화한다.   */
/*   numLeft 를 total 로 초기화한다.        */
/************************************************************************/
void init(int *list, int n, int total)
{
 int i;
 for(i = 0 ; i < n ; i++)
 {
  *(list + i) = i;   // 인덱스를 순서대로 저장. 0, 1, 2,..
 }
 numLeft = total;    // 처음 남아있는 순열의 개수는 총 개수

 
}

/************************************************************************/
/* 함수명 : factorial                                                  */
/* 팩토리얼을 구해주는 함수            */
/************************************************************************/
int factorial(int n)
{
 int i, f = 1;

 for(i = n ; i > 0 ; i--)
 {
  f = f * i;
 }
 return f;
}


 

Posted by 행복한 프로그래머 궁금쟁이박

댓글을 달아 주세요