본문 바로가기
[C++] 알고리즘 교육/7~8. 재귀함수

[알고리즘 8.1.1] 재귀함수 - 순열 구하기

by 안산학생 2019. 4. 25.

문제


서로 다른 n개의 원소들 중에서 r개만을 뽑아 일렬로 나열하는 것을 순열이라 한다. 예를 들어, 3개의 원소 a, b, c 중에서 2개만을 뽑아 나열하면 ab, ac, ba, bc, ca, cb 의 6가지 경우가 있다. n과 r이 주어질 때, n개의 소문자 중에서 r개만을 뽑아 나열하는 모든 경우를 출력하는 프로그램을 작성하시오. 단, a부터 시작하여 연속으로 n개의 알파벳을 갖고 있다고 하자.  

입력


첫 번째 줄에 n과 r이 주어진다. ( 1 ≤ n ≤ 10, 0 ≤ r ≤ min(n, 7) )  

출력


각 줄에 n개의 소문자 중에서 r개만을 뽑아 나열하는 경우를 사전순으로 나열한 결과를 출력한다.

 

예제 입력

4 2

예제 출력

ab

ac

ad

ba

bc

bd

ca

cb

cd

da

db

dc

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
 
const int max = 100;
int n, r;
char arr[max];
int check[max];
 
void bf(int x){
  if(x>=r){
    printf("%s\n",arr);
  }else{
    for(int i=0; i<n; i++){
      char alpha = 'a'+i;
      if(check[i] == false){
        arr[x] = alpha;
        check[i] = true;
        bf(x+1);
        arr[x] = 0;
        check[i] = false;
      }
    }
  }
}
 
int main(){
  
  scanf("%d %d",&n, &r);
  bf(0);
  
  
  return 0;
}

댓글