[Algorithm] 순열과 조합 그리고 중복 순열, 중복 조합까지 with Java

1. 순열(Permutation)

순열은 주어진 N개의 원소 중에서 R개를 뽑아 순서를 고려하여 나열하는 경우의 수를 의미한다.

즉, N개의 요소에서 R개를 선택하여 나열하는 방법의 수이다.

순열의 수식

5개중 3개를 뽑는 순열의 예시

순열 구현 (Java, 재귀함수 이용)

import java.util.Arrays;
import java.util.Scanner;

public class Permutation {

    private static int N;
    private static int R;
    private static int[] numbers; // 하나의 경우를 담는 배열
    private static int[] input; // 원소들을 저장할 배열

    // cnt: 현재까지 뽑은 수의 개수
    private static void permutation(int cnt) {
        if (cnt == R) {
            System.out.println(Arrays.toString(numbers));
            return;
        }

        for (int i = 0; i < N; i++) {
            numbers[cnt] = input[i];
            permutation(cnt + 1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        R = sc.nextInt();
        numbers = new int[R];
        input = new int[N];

        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }
        permutation(0);
    }
}

 

2. 조합(Combination)

조합은 순열과 다르게 원소의 순서를 고려하지 않고 N개의 원소 중 R개를 뽑는 경우의 수를 의미한다.

순열과 달리 조합에서는 한 번 뽑힌 원소가 다시 선택되지 않는다.

조합의 수식

5개중 3개를 뽑는 조합의 예시

 

조합 구현 (Java, 재귀함수 이용)

import java.util.Arrays;
import java.util.Scanner;

public class Combination {

    private static int N;
    private static int R;
    private static int[] numbers;
    private static int[] input;

    private static void combination(int cnt, int start) {
        if (cnt == R) {
            System.out.println(Arrays.toString(numbers));
            return;
        }

        for (int i = start; i < N; i++) {
            numbers[cnt] = input[i];
            combination(cnt + 1, i + 1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        R = sc.nextInt();
        totalCnt = 0;
        numbers = new int[R];
        input = new int[N];

        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }
        combination(0, 0);
    }
}

 

3. 중복 순열(Repeated Permutation)

중복 순열은 원소를 선택할 때 같은 원소를 여러번 선택할 수 있는 순열이다.

중복순열의 수식

5개중 3개를 뽑는 중복순열의 예시

중복 순열 구현 (Java, 재귀함수 이용)

import java.util.Arrays;
import java.util.Scanner;

public class Permutation_중복 {

    private static int N;
    private static int R;
    private static int[] numbers;
    private static int[] input;

    private static void permutation(int cnt) {
        if (cnt == R) {
            System.out.println(Arrays.toString(numbers));
            return;
        }

        for (int i = 0; i < N; i++) {
            numbers[cnt] = input[i];
            permutation(cnt + 1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        R = sc.nextInt();
        numbers = new int[R];
        input = new int[N];

        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }
        permutation(0);
    }
}

 

4. 중복 조합(Repeated Combination)

중복 조합은 원소를 선택할 때 같은 원소를 여러 번 선택할 수 있는 조합이다. 

중복 조합의 수식

7개중 3개를 뽑는 중복 조합의 예시

중복 조합 구현 (Java, 재귀함수 이용)

import java.util.Arrays;
import java.util.Scanner;

public class Combination_중복 {

    private static int N;
    private static int R;
    private static int[] numbers;
    private static int[] input;

    private static void combination(int cnt, int start) {
        if (cnt == R) {
            System.out.println(Arrays.toString(numbers));
            totalCnt++;
            return;
        }

        for (int i = start; i < N; i++) {
            numbers[cnt] = input[i];
            combination(cnt + 1, i);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        R = sc.nextInt();
        input = new int[N];
        numbers = new int[R];

        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }
        combination(0, 0);
    }
}

 

정리

• 순열: 원소의 순서를 고려하여 선택
• 조합: 원소의 순서를 고려하지 않고 선택
• 중복 순열: 같은 원소를 여러 번 선택 가능
• 중복 조합: 같은 원소를 여러 번 선택하면서도 조합으로 계산