C언어 - 순열 알고리즘 [nPr]

경우의 수 순열을 프로그래밍화 (나열, 카운팅)

 

순열이란?

 - 서로다른 n개에서 중복 없이 r개를 택하여 나열하는것을 순열이라 한다. nPr (Permutation)

 

구현 방향

 - n의 원소의 갯수가 늘어날 수록 for문의 중첩이 계속 늘어나야 한다. 

 - for문으로 구현할 경우 중첩이 많아질경우 효율이 떨어지고 n과 r의 값이 변할때마다 코드를 수정해줘야한다.

 - 재귀함수를 사용해서 문제를 풀어보도록 하자.

 

코드

#include <stdio.h>

int arr[] = {1,2,3,4}; //전역 변수로선언. 동적 할당이 효율적임

void swap(int *a, int *b ){  //값을 이동하기 위한 함수
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void print_arr(int size){  //값을 프린트 하기위한 함수
    for(int i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

void permutation(int n, int r, int depth){ //재귀함수 함수
    if( r == depth){   //r이 depth(0) 일때 출력함수 호출
        print_arr(depth);
        return;
    }
    for(int i=depth; i<n; i++){
        swap(&arr[i], &arr[depth]);
        permutation(n, r, depth+1);
        swap(&arr[i], &arr[depth]); //배열을 재자리로 보내주기 >위함
    }
}

int main() {
    permutation(sizeof(arr)/sizeof(int), 4, 0);
    return 0;
}

n과 r의 값이 변할때마다 코딩을 수정해야한다.

다음엔 동적 할당을 활용해 배열을 할당해보도록 하자!

swap 함수가 코딩으로만 보면 이해가 어렵기 때문에 한번쯤 3P3 혹은 3P2 간단한 수로 직접 적어가면서 흐름을 파악하는게 큰 효과가 있다.

 

C언어 - malloc, free, sizeof 를 이용한 동적 할당을 이용하여

 

#include <stdio.h>
#include <stdlib.h> //malloc 함수 

int *arr;//배열 선언
void swap(int *a, int *b);
void print_arr(int c);
void Permutation(int n, int r, int depth);

int main(){
	int n,r;
	
	//n과 r을 공백을 두고 입력받는다
	scanf("%d %d",&n,&r);
	
	//n개 중에서 n개의 배열 할당
	arr = (int*)malloc(n*sizeof(int));
	
	//n배열 값 입력
	for(int i=0;i<n;i++)
		arr[i]=i+1;
	
	Permutation(n,r,0);
	free(arr);//동적 할당 해제
	return 0;
}
void swap(int *a, int *b){//값을 변환해주는 함수
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}
void print_arr(int c){//배열을 프린트해주는 함수
	for(int i=0;i<c;i++){
		printf("%d",arr[i]);
	}
	printf("\n");
}
void Permutation(int n, int r, int depth){
	if(r==depth){
		print_arr(depth);
		return;
	}
	for(int i=depth;i<n;i++){
		swap(&arr[i], &arr[depth]);
		Permutation(n,r,depth+1);
		swap(&arr[i], &arr[depth]);
	}
}

arr배열을 동적으로 할당해주며 초깃값을 설정해주었다.

동적 할당을 활용해 n과r의 값이 변해도 코드가 변하지 않게끔 효율적인 코드를 작성했다.

 

*순열에서 swap 함수를 사용할때 왜 포인터를 사용했는지 설명

C언어 - 포인터 활용, call by value, call by reference

C언어 - malloc, free, sizeof

 

C언어 - 조합 알고리즘 [nCr]