기초수학 - 순열(Permutation)

시작하며.

순열은 코딩 테스트에서 여러가지 유형으로 응용되어 나온다.
개념을 확실히 알고 넘어가기 위해 정리하고자 한다.
순열을 이해하기 전에 팩토리얼을 먼저 알아보자.

 

팩토리얼(Factorial).

팩토리얼은 양의 정수 n에 대해 1부터 n까지의 모든 정수를 곱한 값
n 팩토리얼은 n!으로 표기한다.

// 1에서 n까지의 모든 자연수의 곱 (n!)

1! = 1
2! = 2 X 1
3! = 3 X 2 X 1

n! = n(n-1)(n-2) ... X 1

public class Permutation0603 {
    public static void main(String[] args) {
        // 팩토리얼
        int n = 5;
        int result = 1;
        
		// 반복문으로 구현하기
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        
        System.out.println(factorial(n)); // 120
        System.out.println(result); // 120
    }
	
    // 재귀함수로 구현하기
    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
}

순열(Permutation).

순열(Permutation)은 주어진 원소들로 만들 수 있는 모든 가능한 순서나 배열의 경우의 수를 말한다.
순열은 원소들의 순서가 중요한 경우에 사용되며 주어진 원소들을 나열하는 모든 경우를 고려하며,
원소의 순서가 다르면 서로 다른 순열로 간주한다. 순서가 있고 중복은 허용하지 않는다.

예를 들어, 주어진 세 개의 원소 A, B, C로 만들 수 있는 순열은 
ABC, ACB, BAC, BCA, CAB, CBA로 총 6가지. 
이 때, A와 B, B와 A는 순서가 다르므로 각각 다른 순열로 취급한다.

순열은 수학, 통계, 알고리즘 등 다양한 분야에서 활용되며
문제 해결이나 알고리즘 설계에서 순열을 생성하고 활용하여 원하는 결과를 얻을 수 있다.
자바에서는 재귀 함수나 반복문을 사용하여 순열을 생성하고 처리할 수 있다.

- 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 O, 중복 X)
case1. 5명을 3줄로 세우는 방법
case2. 서로 다른 4명 중 반장, 부반장을 뽑는 방법 

 

        // 순열 - 5명을 3명으로 세우는 경우의 수
        int n = 5;
        int r = 3;
        int result = 1;

        for (int i = n; i >= n - r + 1; i--) {
            result *= i;
        }

        System.out.println(result); // 60

 

중복 순열(Permutation with Repetition).

중복 순열(Permutation with Repetition)은 원소의 중복이 허용되는 순열
주어진 원소들 중에서 중복을 허용하여 순서에 따라 나열하는 것을 의미

예를 들어, 주사위를 던져서 나오는 눈금을 순서에 따라 나열하는 경우는
중복 순열을 구하려면 각 위치(던질 횟수)에 1부터 6까지의 숫자를 중복해서 넣을 수 있다.
따라서 중복 순열의 경우 주사위를 던지는 횟수에 따라 가능한 모든 경우의 수를 구할 수 있다.

- 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 O, 중복 O)
case1. 서로 다른 4래의 수 중 2개를 뽑는 방법(중복 허용)
case2. 후보는 2명, 투표자 3명일 때 이름을 적어 투표하는 방법

        // 중복 순열 - 서로 다른 4개의 수 중 2개를 뽑는 경우의 수 (중복 허용)
        n = 4;
        r = 2;
        result = 1;

        for (int i = 0; i < r; i++) {
            result *= n;
        }
        System.out.println(result); // 16

        System.out.println((int) Math.pow(n, r)); // 16

 

원 순열(Circular Permutation).

원순열(Circular Permutation)은 원형으로 배치된 원소들의 순열
원순열은 일반적인 순열과 달리 원형으로 배치된 원소들을 회전시켜 나열하는 것을 의미
첫 번째 원소를 기준으로 회전하면서 가능한 모든 순열을 구한다.

예를 들어, 3개의 원소 A, B, C로 이루어진 원순열은 ABC, BCA, CAB
원순열은 주로 시계 방향 또는 반시계 방향으로 원을 형성하는 문제에 활용.

- 원 모양의 테이블에 n개의 원소를 나열하는 경우의 수
case1. 원 모양의 테이블에 3명을 앉히는 경우  

        // 원순열 - 원 모양의 테이블에 3명을 앉히는 경우의 수
        n = 3;
        result = 1;

        for (int i = 1; i < n; i++) {
            result *= i;
        }
        System.out.println(result); // 2