팩토리얼(Factorial)

• 1에서 n까지 모든 자연수의 곱 (n!)
  • 1! = 1
  • 2! = 1 x 2
  • 3! = 1 x 2 x 3

n! = n(n - 1)(n-2)…1

순열이란?

순열은 원소들의 순서를 고려하여 배열하는 것을 말합니다. 예를 들어, {1, 2, 3}이라는 세 개의 숫자가 주어졌을 때, 가능한 모든 순열은 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}입니다.

$_{n}P_r\ =\ \frac{n!}{(n-r)!}\ =\ n(n - 1)(n-2)...(n-r+1)$ (단, 0 < r ≤ n)

중복 순열

• 서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 O, 중복 O)
  - 예시) 서로 다른 4개의 수 중 2개를 뽑는 방법 (중복 허용)
  - 예시) 후보 2명, 유권자 3명일 때 기명 투표 방법

  $_{n}\prod_r\ =\ n^r$

원 순열

• 원 모양의 테이블에 n개의 원소를 나열하는 경우의 수
  • 예시) 원 모양의 테이블에 3명을 앉히는 경우

$\frac{n!}{n}\ =\ (n-1)!$

자바에서 순열 구현하기

import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {

//      1. 팩토리얼
        System.out.println("== 팩토리얼 ==");
//      5!
        int n = 5;
        int result = 1;

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

        System.out.println(IntStream.range(2, 6).reduce(1, (x, y) -> (x * y)));

//      2. 순열
        System.out.println("== 순열 ==");
//      5명을 3줄로 세우는 경우의 수
        n = 5;
        int r = 3;
        result = 1;

        for (int i = n; i >= n - r + 1; i--) {
            result *= i;
        }
        System.out.println("result = " + result);

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

        for (int i = 0; i < r; i++) {
            result *= n;
        }
        System.out.println("result = " + result);
        System.out.println(Math.pow(n, r));

//      4. 원 순열
        System.out.println("== 원 순열 ==");
//      원 모양의 테이블에 3명을 앉히는 경우의 수
        n = 3;
        result = 1;

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

// 1, 2, 3, 4 를 이용하여 세자리 자연수를 만드는 방법 (순서 O, 중복 x)의 각 결과를 출력하시오
// 방법 1

public class Practice1 {
    void permutation(int[] arr, int depth, int n, int r) {
        if (depth == r) {
            for (int i = 0; i < r; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = depth; i < n; i++) {
            swap(arr, depth, i);
            permutation(arr, depth + 1, n, r);
            swap(arr, depth, i);
        }
    }

    void swap(int[] arr, int depth, int idx) {
        int tmp = arr[depth];
        arr[depth] = arr[idx];
        arr[idx] = tmp;
    }


    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};

        Practice1 p = new Practice1();
        p.permutation(arr, 0, 4, 3);
    }
}

// 1, 2, 3, 4 를 이용하여 세자리 자연수를 만드는 방법 (순서 O, 중복 x)의 각 결과를 출력하시오
// 방법 2

import java.util.Arrays;

public class Practice2 {
    void permutation(int[] arr, int depth, int n, int r, boolean[] visited, int[] out) {
        if (depth == r) {
            System.out.println(Arrays.toString(out));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                out[depth] = arr[i];
                permutation(arr, depth + 1, n, r, visited, out);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        int n = 4;
        int r = 3;
        int[] arr = {1, 2, 3, 4};
        boolean[] visited = new boolean[n];
        int[] out = new int[r];

        Practice2 p = new Practice2();
        p.permutation(arr, 0, n, r, visited, out);
    }
}