[C] 조합, 순열, 중복조합, 중복순열

조합, 순열, 중복조합, 중복순열은 모두 n 개의 item에서 m개를 뽑고자 하는 경우이다. 즉, 4가지 경우 함수의 모양이 조금 다를 뿐 큰 틀은 같다.

 

• 조합(combination) : 순서와 상관없다. (0 1 2 와 2 1 0 은 같은 수로 여긴다)
• 순열(permutation) : 순서에 상관있다. (0 1 2 와 2 1 0 은 다른 수로 여긴다)
• 중복조합 : 조합이되 중복된 수가 나올 수 있다. 즉, 같은 item을 여러번 뽑을 수 있다.
• 중복순열: 순열이되 중복된 수가 가능하다. 즉, 같은 item을 여러번 뽑을 수 있다.

문제의 해결 순서

1. m개를 뽑을 공간을 미리 할당한다. (bucket)
2. m을 뽑을 함수 (pick 함수)의 모양은 ' pick(item 정보, bucket 정보, k(앞으로 뽑아야할 숫자의 개수)) '
3. pick 함수는 다음과 같이 구현될 수 있다.

- k : 앞으로 뽑아야 할 숫자의 개수

- Trivial case // if (k==0) : 숫자를 모두 뽑은 경우이므로, 완성한 경우의 수를 출력하고 return 한다. (함수의 무한 호출을 막기 위해)

- Recursive case // if (k>0) : 앞으로 k개를 뽑아야 하므로 일단 1개를 뽑고 같은 함수를 순환 호출하여 k-1개를 뽑는다. 즉, pick 함수 안에서 pick(item 정보, bucket 정보, k-1)을 호출한다.

 

여기서 pick이 구현되는 방법은 위 4가지마다 조금씩 다르다.

 

pick 함수의 큰 모양

pick (int items[], int itemSize, int bucket[], int bucketSize, int k){
      if (k==0){
      	printf(   )
        return; //순환 호출에서 무한 호출을 막기 위함
      }
      
      for item from candidate items //아이템 후보 중에 아이템 뽑기
      {
      	bucket[아이템이 들어갈 자리] = item; //아이템
        pick(items, bucket, bucketSize, k-1); //k-1개를 뽑기 -> 권력 이양
      }
}       

 

조합

0부터 n개의 원소(0~n-1) 중에서 3개를 골라 출력하는 코드를 작성하시오.

 

- 후보 아이템은 0~n-1 // int itemSize = n;

- bucket은 정수 3개를 담을 수 있는 배열 //int bucket[3];

 

조합은 0, 1, 2와 2, 1, 0을 같은 수로 고려하기 때문에 뽑을때 오름차순 혹은 내림차순으로 뽑아서 똑같은 경우를 뽑는 것이 사라지게끔 한다.

 

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

void pick(int n, int* bucket, int bucketSize, int k) {
	int i, lastIndex, smallest, item;
	if (k == 0) { //모두 뽑은 경우 print하고 return
		for (i = 0; i < bucketSize; i++)
			printf("%d ", bucket[i]);
		printf("\n");
		return;
	}
	lastIndex = bucketSize - k - 1; // 가장 최근에 뽑힌 수가 저장된 위치 index
	if (bucketSize == k) //처음 뽑는 경우
		smallest = 0;
	else
		smallest = bucket[lastIndex] + 1; //중복을 막기 위해 오름차순으로 뽑는다.
        								  //바로 전에 뽑은 수에 +1
	for (item = smallest; item < n; item++) { //smallest에서 n-1까지의 수에서 뽑는 경우
		bucket[lastIndex + 1] = item;
		pick(n, bucket, bucketSize, k - 1); //1개를 뽑았으므로 k-1개를 뽑는다
	}
}

int main(void) {
	int n, k;

	printf("Enter n: "); //n(0~n-1까지의 수) k(뽑을 수의 개수)를 사용자에게 입력받아
	scanf("%d", &n);
	printf("Enter k: ");
	scanf("%d", &k);

	int *bucket = (int*)malloc(sizeof(int)*k); //buckek 배열을 동적할당
	pick(n, bucket, k, k);

	free(bucket);
}

입력 :

Enter n : 5

Enter k : 3

 

출력 : 

 

중복조합

큰 틀은 조합과 같지만, 중복된 수를 뽑을 수 있다. 즉, 그 전 수와 같거나 큰 수를 뽑으면 된다.

 

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

void pick(int n, int* bucket, int bucketSize, int k) {
	int i, lastIndex, smallest, item;
	if (k == 0) { //모두 뽑은 경우 print하고 return
		for (i = 0; i < bucketSize; i++)
			printf("%d ", bucket[i]);
		printf("\n");
		return;
	}
	lastIndex = bucketSize - k - 1; // 가장 최근에 뽑힌 수가 저장된 위치 index
	if (bucketSize == k) //처음 뽑는 경우
		smallest = 0;
	else
		smallest = bucket[lastIndex]; //그 전수와 같거나 크면 된다.
        
	for (item = smallest; item < n; item++) { //smallest에서 n-1까지의 수에서 뽑는 경우
		bucket[lastIndex + 1] = item;
		pick(n, bucket, bucketSize, k - 1); //1개를 뽑았으므로 k-1개를 뽑는다
	}
}

int main(void) {
	int n, k;

	printf("Enter n: "); //n(0~n-1까지의 수) k(뽑을 수의 개수)를 사용자에게 입력받아
	scanf("%d", &n);
	printf("Enter k: ");
	scanf("%d", &k);

	int *bucket = (int*)malloc(sizeof(int)*k); //buckek 배열을 동적할당
	pick(n, bucket, k, k);

	free(bucket);
}

 

입력 :

Enter n : 5

Enter k : 3

 

출력:

 

중복순열

순서 상관있고, 중복이 가능하기 떄문에 매번 전체 아이템중에서 뽑는다.

 

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

void pick(int n, int* bucket, int bucketSize, int k) {
	int i, lastIndex, smallest, item;
	if (k == 0) { //모두 뽑은 경우 print하고 return
		for (i = 0; i < bucketSize; i++)
			printf("%d ", bucket[i]);
		printf("\n");
		return;
	}
	lastIndex = bucketSize - k - 1; // 가장 최근에 뽑힌 수가 저장된 위치 index
    
    smallest = 0; //매번 전체 아이템에서 뽑기때문에
        
	for (item = smallest; item < n; item++) { //smallest에서 n-1까지의 수에서 뽑는 경우
		bucket[lastIndex + 1] = item;
		pick(n, bucket, bucketSize, k - 1); //1개를 뽑았으므로 k-1개를 뽑는다
	}
}

int main(void) {
	int n, k;

	printf("Enter n: "); //n(0~n-1까지의 수) k(뽑을 수의 개수)를 사용자에게 입력받아
	scanf("%d", &n);
	printf("Enter k: ");
	scanf("%d", &k);

	int *bucket = (int*)malloc(sizeof(int)*k); //buckek 배열을 동적할당
	pick(n, bucket, k, k);

	free(bucket);
}

 

입력 :

Enter n : 5

Enter k : 3

 

출력:

 

 

순열

순열은 순서에 상관 있고, item이 중복되지 않기 때문에 전에 나온 아이템 중 나오지 않은 아이템을 뽑아야한다.

 

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

void pick(int *bucket, int n, int bucketSize, int k){
	int i, lastIndex, smallest, item;

	if (k == 0) {// 고를 것이 없으면 출력
		for (i = 0; i < bucketSize; i++)
			printf("%d ", bucket[i]);
		printf("\n");
		return;
	}

	lastIndex = bucketSize - k - 1; //picked array에서 마지막에 채워진 element의 index
	smallest = 0; //순열은 매번 전체 아이템에서 시작함

	for (item = smallest; item < n; item++) {
		int chosen = 0; //이미 뽑혔는지를 검사하기 위한 flag변수
        				//처음엔 false(0)으로 둔다.

		for (int j = 0; j <= lastIndex; j++) {
			if (bucket[j] == item) { //item이 이미 뽑힌 상태이면
				chosen = 1; //뽑힌 상태이므로 true(1)로 값을 바꾸고
				break; //멈춤
			}
		}

		if (chosen) 
			continue; //나왔으면 그 다음 아이템으로 넘어간다

		bucket[lastIndex + 1] = item; //나오지 않은 아이템을 넣는다
		pick(bucket, n, bucketSize, k - 1);
	}
}

int main(void) {
	int n, k;

	printf("Enter n: ");
	scanf("%d", &n);
	printf("Enter k: ");
	scanf("%d", &k);

	int *bucket = (int*)malloc(sizeof(int)*k);
	pick(bucket, n, k, k);

	free(bucket);
}

 

입력 :

Enter n : 5

Enter k : 3

 

출력: