C 언어, 순열 자료 출력하기

순열을 구하는 C 예제

 

작성. 오상문 sualchi@daum.net

 

 

[참고] 순열과 조합에 대한 내용은 아래 글을 찹조하세요.

http://blog.daum.net/sualchi/13720444

 

 

순열 예제는 3개 파일로 구성됩니다.

 

(1) permutation.c : 순열을 다루는 함수 구현부 (2) permutation.h : 순열 다루는 함수 헤더 파일 (3) permutation_main.c : 순열 구하는 함수를 다루는 예제 파일

 

 

먼저

permutation_main.c 파일부터 살펴보겠습니다.

 

데모 예제에는 "permutation.h"가 추가되어 있습니다.  

이 데모 프로젝트에 "permutation.c" 파일과 헤더 파일을 추가하고 컴파일 하면 됩니다.  (아래 소스 참고)

 

// 순열 구하여 출력하는 예제

// 파일명: permutation_main.c

 

#include <stdio.h>
#include <stdlib.h>
#include "permutation.h"

 

// 순열 자료를 구할 데이터 개수 
#define COUNT 5
int data[COUNT] = {1,2,3,4,5};  // 순열 자료를 구할 데이터 배열 

 

int main(void)
{
 // 순열 자료 구조 생성 및 초기화
 newPermutation(COUNT, data);  //  n P r  -->  COUNT P r
 
 permutation(3);   // 5 P 3 
 
 // 순열 자료 구조 해제  
 delPermutation();
 
 //system("PAUSE");
 return 0;
}

//-------------------------------------------------------------------

 

<실행 화면> 4P3 화면...  4개 중에서 3개를 골라서 출력하는 순열

 

 

 

// permutation.h 헤더 파일

#ifndef PERMUTATION
#define PERMUTATION
 
int  newPermutation(int count, int data[]);
void pushPcheck(int index);
int  popPcheck(void);
void printPcheck(void);
void permutation(int r);
int isExistPcheck(int index);

#endif

//-----------------------------------------------------------------------------------------

 

 

// permutation.c 파일  (순열 구하는 함수 구현)

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

int * pData = NULL;  // 데이터 버퍼 포인터
int * pCheck = NULL; // 뽑은 자료를 저장할 체크드 인덱스 버퍼 포인터 (1세트 정보 저장)
int pSize = 0;     // 순열에 제공된  데이터 크기 
int sSize = 0;     // 체크드 인덱스 버퍼 크기(스택 구조로 이용함) 

 

// 순열 계산을 위한 동적 메모리 할당 작업 (데이터와 체크 리스트 버퍼 생성)
// count = 아이템 개수
// data[] = 순열 계산을 위한 정수 데이터 자료  
int newPermutation(int count, int *data)
{
 int i; 
 
 sSize = 0;
 pSize = count;  
 pData = (int *)malloc(count * sizeof(int));
 
 if(pData) {
  pCheck = (int *)malloc(count * sizeof(int));
  if(pCheck) {
   memcpy(pData, data, count * sizeof(int)); 
   for(i = 0; i < count; i++) {
    pCheck[i] = -1;
   }
   return 0;
  }
  free((void*)pData);
 }
 
 return 1;
}

 

// 순열 계산 출력을 위한 동적 메모리를 해제하고 버퍼 크기를 0으로 설정 
void delPermutation(void)
{
 sSize = pSize = 0;
 
 if(pData) {
  free((void *)pData);
 }
 if(pCheck) {
  free((void *)pCheck);
 }
}

 

// 체크드 버퍼에서 자료를 추가 (스택 구조 LIFO)
void pushPcheck(int index)
{
 if(sSize <= pSize) {
  pCheck[sSize++] = index; 
 }
}

 

// 체크드 버퍼에서 자료를 하나 꺼냄 (스택 구조 LIFO)
int popPcheck(void)
{
 int value = -1;
 
 if(sSize > 0) {
  value = pCheck[--sSize];
  pCheck[sSize] = -1;
 } 
 
 return value;   
}

 

// 출력하기 위해 저장한 한 세트 자료 출력
void printPcheck(void)
{
 int i;
 
 if(pSize > 0) {
  for(i = 0; i < sSize; i++) 
   printf("%d ", pCheck[i]);
  printf("\n");
 } else {
  printf("No Check Data!\n");
 }
}

 

// 순열 모든 자료를 구해서 화면에 출력(nPr) --> pSize P r    
void permutation(int r)  
{
 int i;
 
 if(r > 0) { // 아직 순열 1세트가 완성되지 않았으면 
  for(i = 0; i < pSize; i++) {
   if(!isExistPcheck(i)) {
    pushPcheck(i);
    permutation(r - 1);  
   }
  }
 } else { // 순열 1세트가 완성되면 그것을 출력 
  printPcheck();
 }
 
 popPcheck();  
}

 

// 체크드 스택에 인덱스 값이 존재하는가(이미 사용된 인덱스)
int isExistPcheck(int index)
{
 int i;
 
 for(i = 0; i < sSize; i++)
   if(pCheck[i] == index)
    return 1;
    
 return 0;   
}

// The End ----------------------------------------------------------------