순열(Permutation), 팩토리얼(Factorial)

순열

---

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

ex ) 5명을 3줄로 세우기, 서로 다른 4명 중 반장, 부반장 뽑기

 

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

 

 

팩토리얼(Factorial) : 1~n까지 모든 자연수의 곱(n!)
n! = n(n-1)(n-2)...1
ex) 1! = 1
      2! =  1 x 2

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

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

        //스트림 구현
        System.out.println(IntStream.range(2, 6).reduce(1,(x,y) -> (x*y)));
        //reduce : 주어진 함수를 반복 적용 -> 스트림 안의 데이터를 하나로 합침. 1: 초기값

 

중복 순열

---

n개 중 r개 선택(순서O, 중복 O)

ex) 서로 다른 4개 수 중 2개 뽑기( 중복 허용), 후보 2, 유권자 3명일 때 기명투표 방법  --> 2 ∏3 = 2^3 = 8

n∏r = n^r    

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

        for (int i = 0; i < r; i++) {
            result *= n;
        }
        System.out.println("결과: " + result);

        //Math 활용
        System.out.println(Math.pow(n, r));

 

 

원 순열

---

원 모양의 테이블에 n개의 원소를 나열.

ex) 원 모양의 테이블에 3명 앉히기

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

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

 

---

1~4로 세자리 자연수를 만드는 방법 1

    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) {  //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);
        //n 개수 r 자연수자릿수  depth 각 자릿수
    }
}

 

 

재귀함수가 들어가 헷갈리는 부분이 있어 하나씩 설명하자면,

        int[] arr = {1, 2, 3, 4};

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

Practice1 객체 생성 후 permutation 메서드 호출.

이 때, arr = 1,2,3,4  /depth = 0  /n = 4  /r = 3

 

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

처음으로 i = 0, depth = 0 이고 swap을 호출해 depth와 i를 바꾸지만 같으므로 결과는 동일하다. 그리고 다시 permutation을 호출한다.

 

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

여기서 depth 는 1이 되고 i 는 다시 1이 된다. 그리고 다시 permutation을 호출하면 depth는 2가 된다.

 

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

depth는 2, i 는 2 가 되어 permutation 호출, depth = 3

 

   if(depth == r) {
            for (int i = 0; i < r; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;  //재귀함수는 반드시 탈출조건 필요
        }

r이 3이므로 if 문이 실행되어 0,1,2 인덱스가 출력된다. arr 는 1,2,3,4 이므로 123이 출력된다.

 

        for (int i = depth; i < n; i++) {
            swap(arr,depth, i);
            permutation(arr, depth + 1, n, r);  // 여기로 리턴
            swap(arr, depth, i);
        }

permutation으로 돌아와서 depth는 다시 2로 돌아오고 다음을 진행한다.

i가 증가하면서 depth = 2,  i = 3이 되고 2번째와 3번째 자리를 바꿔 arr 는 1243이 된다. 

여기서 다시 permutation 호출 ->  depth = 3

 

    if(depth == r) {
            for (int i = 0; i < r; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }

 

depth가 r가 같으므로 if 문이 실행되어 arr의 0,1,2 인덱스인 124가 출력된다.

그리고 다시 permutation자리로 돌아가 계속 반복하게 된다.

 

마지막엔 아래의 결과값을 도출한다.

1 2 3 
1 2 4 
1 3 2 
1 3 4 
1 4 3 
1 4 2 
2 1 3 
2 1 4 
2 3 1 
2 3 4 
2 4 3 
2 4 1 
3 2 1 
3 2 4 
3 1 2 
3 1 4 
3 4 1 
3 4 2 
4 2 3 
4 2 1 
4 3 2 
4 3 1 
4 1 3 
4 1 2

 

---

2( 쓰이는 곳이 많으니 잘 기억해놓자.)

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

    }

    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[4];

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