Permutation vs Combination & BASEBALL GAME

출처 : 

http://blog.naver.com/PostView.nhn?blogId=bb_&logNo=221338611903&parentCategoryNo=&categoryNo=67&viewDate=&isShowPopularPosts=false&from=section

https://onsil-thegreenhouse.github.io/programming/algorithm/2018/04/05/permutation_combination/

순열과 조합은 다르다. 

예를 들어 int 배열은 {1, 2, 3, 4, 4, 3, 2, 1, 1}, 그리고 선택 개수는 3이라고 하자. 

조합(Combination)하는 경우의 수 : 

2,3,4

1,3,4

1,2,4

1,2,3

순열(Permutation)하는 경우의 수 : 

2,3,4

2,4,3

3,2,4

3,4,2

4,3,2

4,2,3

1,3,4

1,4,3

3,1,4

3,4,1

4,3,1

4,1,3

1,2,4

1,4,2

2,1,4

2,4,1

4,2,1

4,1,2

1,2,3

1,3,2

2,1,3

2,3,1

3,2,1

3,1,2

순열은 순서도 고려하므로 {1, 2,3}과 {2, 1,3}을 다르게 취급한다. 

수학 공식으로는... 순열(nPr)과 조합(nCr) 라고 한다. Permutation vs Combination 

Combination

조합의 공식은.... nCr = n-1Cr-1 + n-1Cr

재귀를 이용해 풀 수 있다. 

아래는 출처에서 제공해주는 소스이다. 

public class Combination {
    public static void main(String[] ar){
        Combination ex = new Combination();
        int[] arr = { 1, 3, 5, 7, 9 };
        int n = arr.length;
        int r = 3;
        int[] combArr = new int[n];

        ex.doCombination(combArr, n, r, 0, 0, arr);
    }

    public void doCombination(int[] combArr, int n, int r, int index, int target, int[] arr){
        if(r == 0){
            for(int i=0; i<index; i++) System.out.print(arr[combArr[i]] + " ");
            System.out.println();
        }else if(target == n) return;
        else{
            combArr[index] = target;
            doCombination(combArr, n, r-1, index+1, target+1, arr); // (i)
            doCombination(combArr, n, r, index, target+1, arr); //(ii)
        }
    }
}

arr[0]부터 arr[4]까지 돌며 뽑는 경우, 안뽑는 경우를 모두 조사

combArr은 빈 배열, 뽑은 원소를 여기에 저장

그러다 끝이 나는 경우는 두가지가 있음.

1) 첫번째는 다 뽑았을 때. 즉, r = 0 

2) r개를 다 못뽑았는데 arr의 모든 원소를 다 검사했을 때. 아무것도 안한다. 

Permutation

nPr을 구현하기 전에 nPn을 구현해보면 이해하기 좋다.

아래는 4P4을 코드로 보여준다 .

public class PermutationNPN {
    public static void main(String[] ar){
        Permutation ex = new Permutation();
        int[] arr = { 1, 2, 3, 4 };
        ex.doPermutation(arr, 0);
    }

    public void doPermutation(int[] arr, int startIdx){
        int length = arr.length;
        if(startIdx == length-1){
            System.out.println();
            return;
        }

        for(int i=startIdx; i<length; i++){
            swap(arr, startIdx, i);
            doPermutation(arr, startIdx+1);
            swap(arr, startIdx, i);
        }
    }

    public void swap(int[] arr, int n1, int n2){
        int temp = arr[n1];
        arr[n1] = arr[n2];
        arr[n2] = temp;
    }
}

먼저 swap()을 통해 (startIdx)번째 자리의 수가 1일때, 2일때, 3일때, 4일때를 조사한다.

(startIdx)번째 자리를 선택한 후, Recursive를 통해 (startIdx+1)번째 자리를 선택하고…이게 반복되다 startIdx가 arr의 마지막 자리를 가리킬 때 끝이 난다.

swap()가 두번 나온 것은 바꿔준 값을 원상복귀하기 위해서이다. 

이제 nPr을 구현해볼 차례!!

위에서 보았던 두 코드를 합치면 nPr이 된다.

nPn + nCr = nPr 

먼저 nCr을 통해 n개 중에 r개를 뽑은 후, 그 r개 수로 이루어진 수열을 doPermutation()으로 정렬해주면 된다. 

public class PermutationNPR {

    public static void main(String[] ar){
        PermutationNPR ex = new PermutationNPR();
        int[] arr = { 1,2,3,4,5,6,7,8,9 };
        int n = arr.length;
        int r = 3;
        int[] combArr = new int[r];
        ex.doCombination(combArr, arr, n, r, 0, 0);
    }

    public void doCombination(int[] combArr, int[] arr, int n, int r, int index, int target){
        if(r == 0){
            doPermutation(combArr, 0);
        }else if(target == n) return;
        else{
            combArr[index] = arr[target];
            doCombination(combArr, arr, n, r-1, index+1, target+1);
            doCombination(combArr, arr, n, r, index, target+1);
        }
    }

    public void doPermutation(int[] arr, int startIdx){
        int length = arr.length;
        if(startIdx == length-1){
            return;
        }

        for(int i=startIdx; i<length; i++){
            swap(arr, startIdx, i);
            doPermutation(arr, startIdx+1);
            swap(arr, startIdx, i);
        }
    }

    private void swap(int[] arr, int n1, int n2){
        int temp = arr[n1];
        arr[n1] = arr[n2];
        arr[n2] = temp;
    }
}

야구게임 풀어보자!

https://programmers.co.kr/learn/courses/30/lessons/42841?language=java

public class Baseball {
/*
숫자 야구 게임이란 2명이 서로가 생각한 숫자를 맞추는 게임입니다. 게임해보기

각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤 서로에게 3자리의 숫자를 불러서 결과를 확인합니다.
그리고 그 결과를 토대로 상대가 정한 숫자를 예상한 뒤 맞힙니다.

* 숫자는 맞지만, 위치가 틀렸을 때는 볼
* 숫자와 위치가 모두 맞을 때는 스트라이크
* 숫자와 위치가 모두 틀렸을 때는 아웃
예를 들어, 아래의 경우가 있으면

A : 123
B : 1스트라이크 1볼.
A : 356
B : 1스트라이크 0볼.
A : 327
B : 2스트라이크 0볼.
A : 489
B : 0스트라이크 1볼.
이때 가능한 답은 324와 328 두 가지입니다.

질문한 세 자리의 수, 스트라이크의 수, 볼의 수를 담은 2차원 배열 baseball이 매개변수로 주어질 때,
가능한 답의 개수를 return 하도록 solution 함수를 작성해주세요.

제한사항
질문의 수는 1 이상 100 이하의 자연수입니다.
baseball의 각 행은 [세 자리의 수, 스트라이크의 수, 볼의 수] 를 담고 있습니다.
입출력 예
baseball   return
[[123, 1, 1], [356, 1, 0], [327, 2, 0], [489, 0, 1]]   2
입출력 예 설명
문제에 나온 예와 같습니다.
 */

    public static void main(String[] args) {
        int[][] arr1 = {
            {123, 1, 1},
            {356, 1, 0},
            {327, 2, 0},
            {489, 0, 1}
        };

        if (2 == new Baseball().solution(arr1)) {
            System.out.println("1 succeeded");
        }
    }

    private int count;
    private int[][] baseball;

    public int solution(int[][] arr1) {
        count = 0;
        baseball = arr1;
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int n = arr.length;
        int r = 3;
        int[] combArr = new int[r];
        doCombination(combArr, arr, n, r, 0, 0);

        System.out.println("$$$$$$$$$$$$$$$$$$$$ count: " + count);
        return count;
    }

    private void doCombination(int[] combArr, int[] arr, int n, int r, int index, int target) {
        if (r == 0) {
            doPermutation(combArr, 0);
        } else if (target == n) {
            return;
        } else {
            combArr[index] = arr[target];
            doCombination(combArr, arr, n, r - 1, index + 1, target + 1);
            doCombination(combArr, arr, n, r, index, target + 1);
        }
    }

    public void doPermutation(int[] arr, int startIdx) {
        int length = arr.length;
        if (startIdx == length - 1) {
            for (int n : arr) {
                System.out.print(n + " ");
            }
            System.out.println();
            gameChecker(arr);
            return;
        }

        for (int i = startIdx; i < length; i++) {
            swap(arr, startIdx, i);
            doPermutation(arr, startIdx + 1);
            swap(arr, startIdx, i);
        }
    }

    private void swap(int[] arr, int n1, int n2) {
        int temp = arr[n1];
        arr[n1] = arr[n2];
        arr[n2] = temp;
    }

    private void gameChecker(int[] res) {
        boolean isAllSame = true;
        for (int i = 0; i < baseball.length; i++) {
            int[] shots = toIntArray(baseball[i][0]);
            int strike = baseball[i][1];
            int ball = baseball[i][2];

            int realS = 0;
            int realB = 0;
            for (int j = 0; j < shots.length; j++) {
                if (shots[j] == res[j]) {
                    realS++;
                    continue;
                }
                for (int k = 0; k < res.length; k++) {
                    if (shots[k] != res[k] && shots[j] == res[k]) {
                        realB++;
                        break;
                    }
                }
            }
            if (realS != strike || realB != ball) {
                isAllSame = false;
            }
        }
        if (isAllSame) {
            count++;
        }
    }

    private int[] toIntArray(int some) {
        String str = String.valueOf(some);
        int[] shots = new int[str.length()];
        for (int j = 0; j < str.length(); j++) {
            shots[j] = str.charAt(j) - '0';
        }
        return shots;
    }
}