순열 (Permutaion)

팩토리얼(Factorial) : 1에서 n까지 모든 자연수의 곱 (n!)

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

순열 : 서로 다른 n개 중에, r개를 선택하는 경우의 수 (순서 O, 중복 X)

• 5명을 3줄로 세우는 방법
• 서로 다른 4명 중 반장, 부반장 뽑는 방법
  
  
  
  
  
• 5개 중, 3개를 뽑는 방법 과 5개를 3줄로 세우기가 같다는 것이 이해가 되지 않아, 적은 숫자들로 노가다를 해보았다. 학생 때, 순열과 조합은 항상 한 번 더 생각했어야 하는 그런 존재였었지... 이렇게 둘이 결국 경우의 수 차원에서는 같다는 걸 확인을 해야 직성에 풀린다.
  
  
  
  
  

중복 순열 : 서로 다른 n개 중에, r개를 선택하는 경우의 수 (순서 O, 중복 O)

• 서로 다른 4개의 수 중, 2개를 뽑는 방법 (중복 허용)

• 후보 2명, 유권자 3명일 때, 기명 투표 방법

  ![image](https://user-images.githubusercontent.com/62336151/186179612-0881b920-eeb9-4ad1-b955-7ac40ce814b9.png)

  
  
  

원 순열 : 원 모양의 테이블에 n개의 원소를 나열하는 경우의 수

• 원 모양의 테이블에 3명을 앉히는 경우

  ![image](https://user-images.githubusercontent.com/62336151/186179976-5a43e808-4849-4d43-ad9f-bcf28f7adf36.png)

  
  
  

예제

import java.util.stream.IntStream;

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

//        팩토리얼
        int n = 5;
        int result = 1;

        for (int i = 1; i <= n ; i++) {
            result *= i;
        }

        System.out.println("result = " + result); // result = 120
        
//        java stream 관련 함수로 팩토리얼 구하기
        System.out.println(IntStream.range(2, 6).reduce(1, (x, y) -> (x * y))); // 120
//        1 * 2 * 3 * 4 * 5  = 120
        
        System.out.println(IntStream.range(1, 2).reduce(1, (x, y) -> (x * y))); // 1 * 1
        System.out.println(IntStream.range(1, 3).reduce(1, (x, y) -> (x * y))); // 1 * 1 * 2
        System.out.println(IntStream.range(10, 13).reduce(10, (x, y) -> (x * y))); // 10 * 10 * 11 * 12
        System.out.println(IntStream.range(10, 13).reduce(10, Integer::sum));// 10 + 10 + 11 + 12
//        IntStream : int 배열을 소스로 하는 스트림
//        range(a, b) : intStream, LongStream 에서 a ~ b 범위의 연속된 정수를 스트림으로 생성, 반환함 -> b 미포함
//        rangeClosed(a, b) : a ~ b 범위의 연속된 정수 반환 -> b 포함
//        reduce : stream 의 요소를 줄여나가면서, 연산을 수행하고, 최종 결과를 반환함
        
//        stream
//        데이터 소스를 추상화하고, 데이터를 다루는데 자주 사용되는 메서드들을 정의해둠.
//        데이터 소스 추상화?
//        데이터 소스가 무엇이던 간에 같은 방식으로 다룰 수 있게 되었음 + 코드의 재사용성 높아짐
//        => stream 을 이용하면, 배열, 컬렉션, 파일에 저장된 데이터도 모두 같은 방식으로 다룰 수 있다.
//        특징
//        1. 데이터 소스 변경 X
//        2. 스트림은 일회용
//        3. 스트림은 작업을 내부 반복으로 처리함 (ex. forEach() )

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

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

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

        for (int i = 0; i < r; i++) { // i = 0 ; i < 2 ; i++ 
            result *= n; // i = 0 , 1
//            i = 0 ; i < 2 ; i++
//            -> i = 0, i = 1
//            1 * 4 * 4 = 16
        }
        System.out.println("result = " + result);
        System.out.println(Math.pow(n, r));

//        원 순열
        n = 3;
        result = 1;

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

연습문제

• 방법 1 : arr의 depth index 자리의 값과 i index 자리의 값을 swap 하여 경우의 수를 계산하는 방식
• 방법 2 : visited[] 라는 배열을 통해 방문 여부름 담아, 순열의 경우의 수를 계산하는 방식

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

import java.util.Arrays;

/**
 * Practice1 : 방법 1
 */
class Practice1 {
    /**
     * permutaion
     * depth = 만드는 수의 자리 수
     * n = 전체 개수
     * r = 뽑는 개수
     */
    void permutaion(int[] arr, int depth, int n, int r) {

//        아래의 반복문을 멈추고 값 출력
        if (depth == r) {
            System.out.println("== 1  ==  depth == r " + "   depth : " + depth);
            for (int i = 0; i < r; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }

//        반복문
        System.out.println("== 1 == depth : " +depth);
        for (int i = depth; i < n; i++) {
            swap(arr, depth, i);
            System.out.println("== 1 == swap 첫 번째 후 arr : " + Arrays.toString(arr));
            permutaion(arr, depth + 1, n, r);
            swap(arr, depth, i);
            System.out.println("== 1 == swap 두 번째 후 arr : " + Arrays.toString(arr));
        }
    }

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

    }

}

/**
 * Practice2 : 방법 2
 */
class Practice2 {
    void permutation(int[] arr, int depth, int n, int r, boolean[] visited, int[] out) {

        if (depth == r) {
            System.out.println("== 2 == depth == r " + depth);
             System.out.println(Arrays.toString(out));
             return;
         }

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

    }

}

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

        Practice1 p = new Practice1();
        System.out.println("========= Practice1 =============");
        p.permutaion(arr, 0, 4, 3);

        int n = 4;
        int r = 3;
        boolean[] visited = new boolean[n];
        int[] out = new int[r];

        System.out.println("========= Practice2 =============");
        Practice2 p2 = new Practice2();
        p2.permutation(arr, 0, n, r, visited, out);
    }
}

방법 1의 출력 값

========= Practice1 =============
== 1 == depth : 0
== 1 == swap 첫 번째 후 arr : [1, 2, 3, 4]
== 1 == depth : 1
== 1 == swap 첫 번째 후 arr : [1, 2, 3, 4]
== 1 == depth : 2
== 1 == swap 첫 번째 후 arr : [1, 2, 3, 4]
== 1  ==  depth == r    depth : 3
1 2 3 
== 1 == swap 두 번째 후 arr : [1, 2, 3, 4]
== 1 == swap 첫 번째 후 arr : [1, 2, 4, 3]
== 1  ==  depth == r    depth : 3
1 2 4 
== 1 == swap 두 번째 후 arr : [1, 2, 3, 4]
== 1 == swap 두 번째 후 arr : [1, 2, 3, 4]
== 1 == swap 첫 번째 후 arr : [1, 3, 2, 4]
== 1 == depth : 2
== 1 == swap 첫 번째 후 arr : [1, 3, 2, 4]
== 1  ==  depth == r    depth : 3
1 3 2 
== 1 == swap 두 번째 후 arr : [1, 3, 2, 4]
== 1 == swap 첫 번째 후 arr : [1, 3, 4, 2]
== 1  ==  depth == r    depth : 3
1 3 4 
== 1 == swap 두 번째 후 arr : [1, 3, 2, 4]
== 1 == swap 두 번째 후 arr : [1, 2, 3, 4]
== 1 == swap 첫 번째 후 arr : [1, 4, 3, 2]
== 1 == depth : 2
== 1 == swap 첫 번째 후 arr : [1, 4, 3, 2]
== 1  ==  depth == r    depth : 3
1 4 3 
== 1 == swap 두 번째 후 arr : [1, 4, 3, 2]
== 1 == swap 첫 번째 후 arr : [1, 4, 2, 3]
== 1  ==  depth == r    depth : 3
1 4 2 
== 1 == swap 두 번째 후 arr : [1, 4, 3, 2]
== 1 == swap 두 번째 후 arr : [1, 2, 3, 4]
== 1 == swap 두 번째 후 arr : [1, 2, 3, 4]
== 1 == swap 첫 번째 후 arr : [2, 1, 3, 4]
== 1 == depth : 1
== 1 == swap 첫 번째 후 arr : [2, 1, 3, 4]
== 1 == depth : 2
== 1 == swap 첫 번째 후 arr : [2, 1, 3, 4]
== 1  ==  depth == r    depth : 3
2 1 3 
== 1 == swap 두 번째 후 arr : [2, 1, 3, 4]
== 1 == swap 첫 번째 후 arr : [2, 1, 4, 3]
== 1  ==  depth == r    depth : 3
2 1 4 
== 1 == swap 두 번째 후 arr : [2, 1, 3, 4]
== 1 == swap 두 번째 후 arr : [2, 1, 3, 4]
== 1 == swap 첫 번째 후 arr : [2, 3, 1, 4]
== 1 == depth : 2
== 1 == swap 첫 번째 후 arr : [2, 3, 1, 4]
== 1  ==  depth == r    depth : 3
2 3 1 
== 1 == swap 두 번째 후 arr : [2, 3, 1, 4]
== 1 == swap 첫 번째 후 arr : [2, 3, 4, 1]
== 1  ==  depth == r    depth : 3
2 3 4 
== 1 == swap 두 번째 후 arr : [2, 3, 1, 4]
== 1 == swap 두 번째 후 arr : [2, 1, 3, 4]
== 1 == swap 첫 번째 후 arr : [2, 4, 3, 1]
== 1 == depth : 2
== 1 == swap 첫 번째 후 arr : [2, 4, 3, 1]
== 1  ==  depth == r    depth : 3
2 4 3 
== 1 == swap 두 번째 후 arr : [2, 4, 3, 1]
== 1 == swap 첫 번째 후 arr : [2, 4, 1, 3]
== 1  ==  depth == r    depth : 3
2 4 1 
== 1 == swap 두 번째 후 arr : [2, 4, 3, 1]
== 1 == swap 두 번째 후 arr : [2, 1, 3, 4]
== 1 == swap 두 번째 후 arr : [1, 2, 3, 4]
== 1 == swap 첫 번째 후 arr : [3, 2, 1, 4]
== 1 == depth : 1
== 1 == swap 첫 번째 후 arr : [3, 2, 1, 4]
== 1 == depth : 2
== 1 == swap 첫 번째 후 arr : [3, 2, 1, 4]
== 1  ==  depth == r    depth : 3
3 2 1 
== 1 == swap 두 번째 후 arr : [3, 2, 1, 4]
== 1 == swap 첫 번째 후 arr : [3, 2, 4, 1]
== 1  ==  depth == r    depth : 3
3 2 4 
== 1 == swap 두 번째 후 arr : [3, 2, 1, 4]
== 1 == swap 두 번째 후 arr : [3, 2, 1, 4]
== 1 == swap 첫 번째 후 arr : [3, 1, 2, 4]
== 1 == depth : 2
== 1 == swap 첫 번째 후 arr : [3, 1, 2, 4]
== 1  ==  depth == r    depth : 3
3 1 2 
== 1 == swap 두 번째 후 arr : [3, 1, 2, 4]
== 1 == swap 첫 번째 후 arr : [3, 1, 4, 2]
== 1  ==  depth == r    depth : 3
3 1 4 
== 1 == swap 두 번째 후 arr : [3, 1, 2, 4]
== 1 == swap 두 번째 후 arr : [3, 2, 1, 4]
== 1 == swap 첫 번째 후 arr : [3, 4, 1, 2]
== 1 == depth : 2
== 1 == swap 첫 번째 후 arr : [3, 4, 1, 2]
== 1  ==  depth == r    depth : 3
3 4 1 
== 1 == swap 두 번째 후 arr : [3, 4, 1, 2]
== 1 == swap 첫 번째 후 arr : [3, 4, 2, 1]
== 1  ==  depth == r    depth : 3
3 4 2 
== 1 == swap 두 번째 후 arr : [3, 4, 1, 2]
== 1 == swap 두 번째 후 arr : [3, 2, 1, 4]
== 1 == swap 두 번째 후 arr : [1, 2, 3, 4]
== 1 == swap 첫 번째 후 arr : [4, 2, 3, 1]
== 1 == depth : 1
== 1 == swap 첫 번째 후 arr : [4, 2, 3, 1]
== 1 == depth : 2
== 1 == swap 첫 번째 후 arr : [4, 2, 3, 1]
== 1  ==  depth == r    depth : 3
4 2 3 
== 1 == swap 두 번째 후 arr : [4, 2, 3, 1]
== 1 == swap 첫 번째 후 arr : [4, 2, 1, 3]
== 1  ==  depth == r    depth : 3
4 2 1 
== 1 == swap 두 번째 후 arr : [4, 2, 3, 1]
== 1 == swap 두 번째 후 arr : [4, 2, 3, 1]
== 1 == swap 첫 번째 후 arr : [4, 3, 2, 1]
== 1 == depth : 2
== 1 == swap 첫 번째 후 arr : [4, 3, 2, 1]
== 1  ==  depth == r    depth : 3
4 3 2 
== 1 == swap 두 번째 후 arr : [4, 3, 2, 1]
== 1 == swap 첫 번째 후 arr : [4, 3, 1, 2]
== 1  ==  depth == r    depth : 3
4 3 1 
== 1 == swap 두 번째 후 arr : [4, 3, 2, 1]
== 1 == swap 두 번째 후 arr : [4, 2, 3, 1]
== 1 == swap 첫 번째 후 arr : [4, 1, 3, 2]
== 1 == depth : 2
== 1 == swap 첫 번째 후 arr : [4, 1, 3, 2]
== 1  ==  depth == r    depth : 3
4 1 3 
== 1 == swap 두 번째 후 arr : [4, 1, 3, 2]
== 1 == swap 첫 번째 후 arr : [4, 1, 2, 3]
== 1  ==  depth == r    depth : 3
4 1 2 
== 1 == swap 두 번째 후 arr : [4, 1, 3, 2]
== 1 == swap 두 번째 후 arr : [4, 2, 3, 1]
== 1 == swap 두 번째 후 arr : [1, 2, 3, 4]

방법 2의 출력값

========= Practice2 =============
== 2 == i = 0 visited[i] = false arr[i]=1
== 2 == i = 1 visited[i] = false arr[i]=2
== 2 == i = 2 visited[i] = false arr[i]=3
== 2 == depth == r 3
[1, 2, 3]
== 2 == i = 3 visited[i] = false arr[i]=4
== 2 == depth == r 3
[1, 2, 4]
== 2 == i = 2 visited[i] = false arr[i]=3
== 2 == i = 1 visited[i] = false arr[i]=2
== 2 == depth == r 3
[1, 3, 2]
== 2 == i = 3 visited[i] = false arr[i]=4
== 2 == depth == r 3
[1, 3, 4]
== 2 == i = 3 visited[i] = false arr[i]=4
== 2 == i = 1 visited[i] = false arr[i]=2
== 2 == depth == r 3
[1, 4, 2]
== 2 == i = 2 visited[i] = false arr[i]=3
== 2 == depth == r 3
[1, 4, 3]
== 2 == i = 1 visited[i] = false arr[i]=2
== 2 == i = 0 visited[i] = false arr[i]=1
== 2 == i = 2 visited[i] = false arr[i]=3
== 2 == depth == r 3
[2, 1, 3]
== 2 == i = 3 visited[i] = false arr[i]=4
== 2 == depth == r 3
[2, 1, 4]
== 2 == i = 2 visited[i] = false arr[i]=3
== 2 == i = 0 visited[i] = false arr[i]=1
== 2 == depth == r 3
[2, 3, 1]
== 2 == i = 3 visited[i] = false arr[i]=4
== 2 == depth == r 3
[2, 3, 4]
== 2 == i = 3 visited[i] = false arr[i]=4
== 2 == i = 0 visited[i] = false arr[i]=1
== 2 == depth == r 3
[2, 4, 1]
== 2 == i = 2 visited[i] = false arr[i]=3
== 2 == depth == r 3
[2, 4, 3]
== 2 == i = 2 visited[i] = false arr[i]=3
== 2 == i = 0 visited[i] = false arr[i]=1
== 2 == i = 1 visited[i] = false arr[i]=2
== 2 == depth == r 3
[3, 1, 2]
== 2 == i = 3 visited[i] = false arr[i]=4
== 2 == depth == r 3
[3, 1, 4]
== 2 == i = 1 visited[i] = false arr[i]=2
== 2 == i = 0 visited[i] = false arr[i]=1
== 2 == depth == r 3
[3, 2, 1]
== 2 == i = 3 visited[i] = false arr[i]=4
== 2 == depth == r 3
[3, 2, 4]
== 2 == i = 3 visited[i] = false arr[i]=4
== 2 == i = 0 visited[i] = false arr[i]=1
== 2 == depth == r 3
[3, 4, 1]
== 2 == i = 1 visited[i] = false arr[i]=2
== 2 == depth == r 3
[3, 4, 2]
== 2 == i = 3 visited[i] = false arr[i]=4
== 2 == i = 0 visited[i] = false arr[i]=1
== 2 == i = 1 visited[i] = false arr[i]=2
== 2 == depth == r 3
[4, 1, 2]
== 2 == i = 2 visited[i] = false arr[i]=3
== 2 == depth == r 3
[4, 1, 3]
== 2 == i = 1 visited[i] = false arr[i]=2
== 2 == i = 0 visited[i] = false arr[i]=1
== 2 == depth == r 3
[4, 2, 1]
== 2 == i = 2 visited[i] = false arr[i]=3
== 2 == depth == r 3
[4, 2, 3]
== 2 == i = 2 visited[i] = false arr[i]=3
== 2 == i = 0 visited[i] = false arr[i]=1
== 2 == depth == r 3
[4, 3, 1]
== 2 == i = 1 visited[i] = false arr[i]=2
== 2 == depth == r 3
[4, 3, 2]