순열

May 8, 2024

순열

팩토리얼 (Factorial)

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

순열 (Permutation)

순서를 정해서 나열
서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 O, 중복 X)
예시) 5명을 3줄로 세우는 방법
예시) 서로 다른 4명 중 반장, 부반장 뽑는 방법
nPr = 𝑛!/(𝑛−𝑟)!=𝑛(𝑛−1)(𝑛−2)⋯(𝑛−𝑟+1) (단, 0<𝑟≤𝑛)

중복 순열

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

원 순열

원 모양의 테이블에 n개의 원소를 나열하는 경우의 수
예시) 원 모양의 테이블에 3명을 앉히는 경우
𝑛!/𝑛=(𝑛−1)!

import java.util.stream.IntStream;

//  기초 수학 - 순열
public class Practice3 {
    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);

    }
}

== 팩토리얼 ==
result = 120
120
== 순열 ==
result = 60
==중복 순열 ==
result = 16
16.0
== 원 순열 ==
result = 2

IntStream.range(2, 6).reduce(1, (x, y) -> (x * y))는 Java 스트림 API를 사용하여 숫자의 범위를 생성하고 이를 곱하는 연산을 수행하는 코드입니다. 이 코드를 이해하기 위해 다음 단계를 밟아 학습할 수 있습니다.

1. IntStream 이해하기

IntStream은 Java 8에서 도입된 스트림 API의 일부분으로, 기본형 int를 위한 스트림입니다. 스트림은 컬렉션의 반복, 집계, 필터링 등을 함수형 스타일로 처리할 수 있게 해줍니다.

2. IntStream.range() 이해하기

IntStream.range(int startInclusive, int endExclusive) 메서드는 시작 값(포함)과 끝 값(포함하지 않음)을 매개변수로 받아, 해당 범위의 int 값들을 생성하는 스트림을 반환합니다.

예를 들어:

IntStream.range(2, 6).forEach(System.out::println);

출력:

여기서는 2부터 5까지의 숫자가 생성됩니다.

3. reduce() 이해하기

reduce() 메서드는 스트림의 요소들을 결합하여 단일 결과를 생성합니다. 두 가지 버전이 있는데, 하나는 초기값을 받는 버전이고, 다른 하나는 초기값 없이 사용됩니다.

초기값을 받는 버전:
```
T reduce(T identity, BinaryOperator<T> accumulator)
```
identity는 초기값이며, accumulator는 두 개의 인수를 받아 결합된 결과를 반환하는 함수입니다.

4. 예제 코드 분석

int result = IntStream.range(2, 6).reduce(1, (x, y) -> (x * y));

이 코드는 다음을 수행합니다:

IntStream.range(2, 6)은 2, 3, 4, 5의 스트림을 생성합니다.
reduce(1, (x, y) -> (x * y))는 초기값 1과 람다식 (x, y) -> (x * y)을 사용하여 스트림의 모든 요소를 곱합니다.

작동 방식:

초기값 1을 x로 시작합니다.
스트림의 첫 번째 요소 2는 y가 됩니다. 1 * 2는 2입니다.
그다음 2는 x가 되고, 스트림의 두 번째 요소 3이 y가 됩니다. 2 * 3은 6입니다.
계속해서 6은 x가 되고, 스트림의 세 번째 요소 4가 y가 됩니다. 6 * 4는 24입니다.
마지막으로 24는 x가 되고, 스트림의 네 번째 요소 5가 y가 됩니다. 24 * 5는 120입니다.

따라서 result는 120이 됩니다.

전체 과정 정리

IntStream.range(2, 6): 2, 3, 4, 5의 스트림 생성.
reduce(1, (x, y) -> (x * y)): 1을 초기값으로 시작하여 각 요소를 곱함.
연산 과정:
- 초기값 1, 스트림의 첫 번째 요소 2 → 1 * 2 = 2
- 2, 스트림의 두 번째 요소 3 → 2 * 3 = 6
- 6, 스트림의 세 번째 요소 4 → 6 * 4 = 24
- 24, 스트림의 네 번째 요소 5 → 24 * 5 = 120
최종 결과 result는 120.

//1,2,3,4 를 이용하여 세자리 자연수를 만드는 방법(순서 o, 중복 x)의 각 결과를 출력하시오
//방법1
public class Practice3_1 {
    public static void main(String[] args) {
        //Test Code
        int[] arr = {1, 2, 3, 4};

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

    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;
    }
}

import java.util.Arrays;

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

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

    private 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] != true) {
                visited[i] = true;
                out[depth] = arr[i];
                permutation(arr, depth + 1, n, r, visited, out);
                visited[i] = false;
            }
        }
    }
}

[1, 2, 3]
[1, 2, 4]
[1, 3, 2]
[1, 3, 4]
[1, 4, 2]
[1, 4, 3]
[2, 1, 3]
[2, 1, 4]
[2, 3, 1]
[2, 3, 4]
[2, 4, 1]
[2, 4, 3]
[3, 1, 2]
[3, 1, 4]
[3, 2, 1]
[3, 2, 4]
[3, 4, 1]
[3, 4, 2]
[4, 1, 2]
[4, 1, 3]
[4, 2, 1]
[4, 2, 3]
[4, 3, 1]
[4, 3, 2]

첫 번째 레벨의 재귀 호출
첫 번째 반복 (i = 0)
visited = [true, false, false, false]
out = [1, 0, 0]
재귀 호출: permutation(arr, 1, n, r, visited, out)

두 번째 레벨의 재귀 호출
첫 번째 반복 (i = 0)
이미 방문, 건너뜀.

두 번째 반복 (i = 1)
visited = [true, true, false, false]
out = [1, 2, 0]
재귀 호출: permutation(arr, 2, n, r, visited, out)

세 번째 레벨의 재귀 호출
첫 번째 반복 (i = 0)
이미 방문, 건너뜀.

두 번째 반복 (i = 1)
이미 방문, 건너뜀.

세 번째 반복 (i = 2)
visited = [true, true, true, false]
out = [1, 2, 3]
재귀 호출: permutation(arr, 3, n, r, visited, out)

네 번째 레벨의 재귀 호출
depth = 3, r과 같음.
순열 출력: [1, 2, 3]
백트래킹
visited = [true, true, false, false]
out = [1, 2, 0]

i = 3으로 진행.
네 번째 반복 (i = 3)
visited = [true, true, false, true]
out = [1, 2, 4]
재귀 호출: permutation(arr, 3, n, r, visited, out)

네 번째 레벨의 재귀 호출
depth = 3, r과 같음.
순열 출력: [1, 2, 4]
백트래킹
visited = [true, true, false, false]
out = [1, 2, 0]

더 이상 진행할 반복이 없으므로 다시 백트래킹.
두 번째 레벨로 돌아와 다음 반복 진행
visited = [true, false, false, false]
out = [1, 0, 0]

i = 2으로 진행.
세 번째 반복 (i = 2)
visited = [true, false, true, false]
out = [1, 3, 0]
재귀 호출: permutation(arr, 2, n, r, visited, out)

세 번째 레벨의 재귀 호출
첫 번째 반복 (i = 0)
이미 방문, 건너뜀.

두 번째 반복 (i = 1)
visited = [true, true, true, false]
out = [1, 3, 2]
재귀 호출: permutation(arr, 3, n, r, visited, out)

네 번째 레벨의 재귀 호출
depth = 3, r과 같음.
순열 출력: [1, 3, 2]
백트래킹
visited = [true, false, true, false]
out = [1, 3, 0]

i = 3으로 진행.
네 번째 반복 (i = 3)
visited = [true, false, true, true]
out = [1, 3, 4]
재귀 호출: permutation(arr, 3, n, r, visited, out)

네 번째 레벨의 재귀 호출
depth = 3, r과 같음.
순열 출력: [1, 3, 4]
백트래킹
visited = [true, false, true, false]
out = [1, 3, 0]

더 이상 진행할 반복이 없으므로 다시 백트래킹.
두 번째 레벨로 돌아와 다음 반복 진행
visited = [true, false, false, false]
out = [1, 0, 0]

i = 3으로 진행.
네 번째 반복 (i = 3)
visited = [true, false, false, true]
out = [1, 4, 0]
재귀 호출: permutation(arr, 2, n, r, visited, out)

세 번째 레벨의 재귀 호출
첫 번째 반복 (i = 0)
이미 방문, 건너뜀.

두 번째 반복 (i = 1)
visited = [true, true, false, true]
out = [1, 4, 2]
재귀 호출: permutation(arr, 3, n, r, visited, out)

네 번째 레벨의 재귀 호출
depth = 3, r과 같음.
순열 출력: [1, 4, 2]
백트래킹
visited = [true, false, false, true]
out = [1, 4, 0]

i = 2으로 진행.
세 번째 반복 (i = 2)
visited = [true, false, true, true]
out = [1, 4, 3]
재귀 호출: permutation(arr, 3, n, r, visited, out)

네 번째 레벨의 재귀 호출
depth = 3, r과 같음.
순열 출력: [1, 4, 3]
백트래킹
visited = [true, false, false, true]
out = [1, 4, 0]

더 이상 진행할 반복이 없으므로 다시 백트래킹.
첫 번째 레벨로 돌아와 다음 반복 진행
visited = [false, false, false, false]
out = [0, 0, 0]

i = 1으로 진행.
두 번째 반복 (i = 1)
visited = [false, true, false, false]
out = [2, 0, 0]
재귀 호출: permutation(arr, 1, n, r, visited, out)

이와 같은 방식으로, 모든 가능한 순열을 생성하여 출력합니다. 이 과정이 계속 반복되면서 각각의 순열을 생성하고 출력하게 됩니다.

출처 : 제로베이스

순열

순열

팩토리얼 (Factorial)

순열 (Permutation)

중복 순열

원 순열

1. IntStream 이해하기

2. IntStream.range() 이해하기

3. reduce() 이해하기

4. 예제 코드 분석

전체 과정 정리

Leave a comment

You may also enjoy

김태원 8월 특강 정렬

김태원 8월 특강 그리디

스프링 핵심가이드 8주차

스프링 핵심가이드 7주차