순열과 조합

순열과 조합

순열 : 순서를 고려하여 뽑는다.

조합 : 순서와 상관없이 뽑는다.

순열

• n,r을 입력으로 받아서 n개 중에서 r개를 뽑는 순열을 만들어보자.
• LinkedList와 boolean[] check 배열을 사용한다.

[Code]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

/**
 * created by victory_woo
 */
public class PermutationWithLinkedList {
    private static LinkedList<Integer> list;
    private static int[] check;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");
        int n = Integer.parseInt(in[0]);
        int r = Integer.parseInt(in[1]);

        list = new LinkedList<>();
        check = new int[n + 1];
        permutation(n, r);
        //rePermutation(n, r);
    }

    // n개 중 r개를 뽑는 순열.(중복 X)
    // 재귀 호출의 개념을 사용한다.
    private static void permutation(int n, int r) {
        if (list.size() == r) {
            print();
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (check[i] == 0) {
                list.add(i);
                check[i] = 1;
                permutation(n, r);
                check[i] = 0;
                list.removeLast();
            }
        }
    }

  	// 중복을 허용하는 순열.
    private static void rePermutation(int n, int r) {
        if (list.size() == r) {
            print();
            return;
        }

        for (int i = 1; i <= n; i++) {
            list.add(i);
            rePermutation(n, r);
            list.removeLast();
        }
    }

    private static void print() {
        for (int value : list) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

• 중복을 허용하지 않는 순열(permutation)

n : 3, r : 2
1 2 
1 3 
2 1 
2 3 
3 1 
3 2 

• 중복을 허용하는 순열(repermutaiion)

n : 3, r : 2
1 1 
1 2 
1 3 
2 1 
2 2 
2 3 
3 1 
3 2 
3 3 

조합

• n,r을 입력으로 받아서 n개 중에서 r개를 뽑는 조합을 만들어보자.
• comArr 배열을 사용한다.

package 순열과조합;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

/**
 * created by victory_woo on 2020/04/03
 */
public class Combination {
    private static int[] comArr;
    private static LinkedList<Integer> list = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");
        int n = Integer.parseInt(in[0]);
        int r = Integer.parseInt(in[1]);

        // 조합 : 순서는 관심 없고 뽑은 유무만 생각한다.
        comArr = new int[r];
        combination(n, r, 0, 1);
        //reCombination(n, r, 0, 1);

    }

    private static void combination(int n, int r, int index, int target) {
        if (r == 0) {
            print();
            return;
        }

        if (target == n + 1) return;

        comArr[index] = target;
        combination(n, r - 1, index + 1, target + 1); // 뽑는 경우.
        combination(n, r, index, target + 1); // 안뽑는 경우.
    }


    private static void reCombination(int n, int r, int index, int target) {
        if (r == 0) {
            print();
            return;
        }

        if (target == n + 1) return;

        comArr[index] = target;
        reCombination(n, r - 1, index + 1, target); // 뽑는 경우.
        reCombination(n, r, index, target + 1); // 안뽑는 경우.
    }


    private static void print() {
        for (int value : comArr) System.out.print(value + " ");
        System.out.println();
    }
}

• 중복을 허용하지 않는 조합(combination)

n : 3, r : 2
1 2 
1 3 
2 3 

• 중복을 허용하는 조합(reCombination)

n : 3, r : 2
1 1 
1 2 
1 3 
2 2 
2 3 
3 3 

이처럼 조합은 [1,2]와 [2,1]은 순서가 고려되지 않아 같은 구성으로 생각된다.