[필수 문제] 순열 구하기

1. 문제

서로 다른 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

 

 

 

2. 풀이

이 문제는 재귀호출을 이용한 완전탐색 문제다. 동작 과정은 다음과 같다.

permutation(0) - 'a'
   ㄴㅡ permutation(1) - 'b'
      ㄴㅡ permutation(2) - 'ab' 출력
   
permutation(0) - 'a'
   ㄴㅡ permutation(1) - 'c'
      ㄴㅡ permutation(2) - 'ac' 출력
   
permutation(0) - 'a'
   ㄴㅡ permutation(1) - 'd'
      ㄴㅡ permutation(2) - 'ad' 출력
   
permutation(0) - 'b'
   ㄴㅡ permutation(1) - 'a'
      ㄴㅡ permutation(2) - 'ba' 출력

...

idx	result[idx]		isVisited[i]
0	[0]	a	[0]	true
1	[1]	b	[1]	true
2	ab 출력
1	[1]	b	[1]	false
1	[1]	c	[2]	true
2	ac 출력
1	[1]	c	[2]	false
1	[1]	d	[3]	true
2	ad 출력

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static boolean[] isVisited;
    private static char[] result;

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());

        isVisited = new boolean[15];
        result = new char[15];

        int idx = 0;
        permutation(n, r, idx);

        br.close();
        bw.flush();
        bw.close();
    }

    private static void permutation(int n, int r, int idx) {
        if(idx >= r) {
            for(int i = 0; i < r; i++) {
                System.out.print(result[i]);
            }
            System.out.println();
        } else {
            for(int i = 0; i < n; i++) {
                if(!isVisited[i]){
                    result[idx] = (char) (i + (int) ('a'));
                    isVisited[i] = true;
                    permutation(n, r, idx+1);
                    isVisited[i] = false;
                }
            }
        }
    }
}