[알고리즘] 순열 (Permutation)

nPr의 모든 경우를 출력하는 코드이다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); //1부터 n까지의 숫자 중에서
        int r = in.nextInt(); //r개를 뽑는다
        boolean[] visited = new boolean[n];
        int[] selected = new int[r];
        for (int i = 0; i < n; i++) {
            visited[i] = false;
        }
        permutation(selected, visited, n, r, 0);
    }
    static void permutation(int[] selected, boolean[] visited, int n, int r, int num) {
        if (num == r) {
            for (int i = 0; i < r; i++) {
                System.out.print(selected[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < n; i++) {
            if(!visited[i]){
                visited[i] = true;
                selected[num] = i + 1;
                permutation(selected, visited, n, r, num + 1);
                visited[i] = false;
            }
        }
    }
}

permutation 함수의 매개변수인 num은 num번째 숫자를 정하는 것이다.

permutation 함수의 for문은 그 num번째 자리에 1부터 n까지의 숫자 중에 어떤 숫자를 넣을지 정하는 것이다.