서로 다른 n개 중 r개를 뽑아서 나열한 것

조합이란?

서로 다른 n개 중 r개를 순서 없이 골라낸 것

즉, AB != AB와 같이 순서가 의미 있으면 순열이고, AB == BA와 같이 순서가 의미 없으면 조합! 그리고 순열, 조합에서 중복을 허용하면 중복 순열, 중복 조합이라고 부른다.

코드로 구현해보자! (☞ﾟヮﾟ)☞💻

공통 로직

public class 순열 {
    private static int n, m;
    private static int[] arr; // 원소를 저장할 배열
    private static boolean[] visited; // 중복을 제거하기 위한 방문 처리

    public static void main(String[] args) {
        n = 4;
        m = 2;
        arr = new int[m];
        visited = new boolean[n + 1];
        permutation(0);
    }

}

순열

    // 순열
    private static void permutation(int cnt) {
        if (cnt == m) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[cnt] = i;
                permutation(cnt + 1);
                visited[i] = false;
            }
        }
    }

    // 중복 순열 - 중복 제거하는 visited를 쓰지 않음
    private static void repeatedPermutation(int cnt) {
        if (cnt == m) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = 1; i <= n; i++) {
            arr[cnt] = i;
            permutation(cnt + 1);
        }
    }

결과

순열

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

중복 순열

[1, 1] - 중복 존재
[1, 2]
[1, 3]
[1, 4]
[2, 1]
[2, 2]
[2, 3]
[2, 4]
[3, 1]
[3, 2]
[3, 3]
[3, 4]
[4, 1]
[4, 2]
[4, 3]
[4, 4]

조합

    // 조합
    private static void combination(int cnt, int start) {
        if (cnt == m) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = start; i <= n; i++) {
            arr[cnt] = i;
            combination(cnt + 1, i + 1); // 오름차순으로 구하면 중복 체크하지 않아도 됨
        }
    }

    // 중복 조합
    private static void repeatedCombination(int cnt, int start) {
        if (cnt == m) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = start; i <= n; i++) {
            arr[cnt] = i;
            combination(cnt + 1, i); // 중복 허용하니까 비내림차순
        }
    }

결과

조합

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

중복 조합

[1, 1] - 중복 존재
[1, 2]
[1, 3]
[1, 4]
[2, 2]
[2, 3]
[2, 4]
[3, 3]
[3, 4]
[4, 4]

정리!

[1, 2] 와 [2, 1]이 다르면 순열! 비유하자면 반에서 반장, 부반장을 뽑는 것과 같다. [1, 2] 와 [2, 1]이 같으면 조합! 비유하자면 반에서 당번 2명을 뽑는 것과 같다. 두명의 순서가 상관없음

그림은 시계방향(90도)으로 회전하는 것을 그려보았다.

노란 부분을 보자

arr2[0][0] = arr1[2][0] arr2[0][1] = arr1[1][0] arr2[0][2] = arr1[0][0]

arr1 배열의 열 값이 arr2 배열의 행 값으로 들어가고 arr2 배열의 행 값은 arr2 배열의 열 값에 반대로 들어가는 것을 볼 수 있다.

이 규칙을 식으로 만들어보면 요로코롬(●'◡'●)

arr2[i][j] = arr1[n-1-j][i];

자바 코드로 구현해보자!!

int n = 3; //행의 길이
int m = 4; //열의 길이
int num = 1;
int[][] arr1 = new int[n][m];
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        arr1[i][j] = num++;
    }
}

int[][] arr2 = new int[m][n]; // 행, 열을 반대로
for (int i = 0; i < m; i++) { 
    for (int j = 0; j < n; j++) {
        arr2[i][j] = arr1[n - 1 - j][i]; // ##핵심 코드##
    }
}

출력해서 결과를 보면

--arr1-- 1 2 3 4 5 6 7 8 9 10 11 12 --arr2-- 9 5 1 10 6 2 11 7 3 12 8 4

시계방향으로 회전이 되었다!!

하는 김에 반시계 방향도 해보자

arr2[i][j] = arr1[j][m-1-i];

코드

int n = 3;
int m = 4;
int[][] arr1 = new int[n][m];
int num = 1;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        arr1[i][j] = num++;
    }
}

int[][] arr2 = new int[m][n];
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        arr2[i][j] = arr1[j][m - 1 - i]; // ##핵심 코드##
    }
}

결과

--arr1-- 1 2 3 4 5 6 7 8 9 10 11 12 --arr2-- 4 8 12 3 7 11 2 6 10 1 5 9

알고리즘을 풀다가 2차원 배열을 특정 값으로 초기화하는데

Exception in thread "main" java.lang.ArrayStoreException: java.lang.Integer

이런 에러가 떴다!

찾아보니 Arrays.fill은 1차원 배열에서만 사용할 수 있다고 한다.

for (int[] i : a) Arrays.fill(i, -1);

for문을 사용하여 해결하였다.