[알고리즘 기본 스킬] 순열,조합

JAVA 언어를 사용합니다.

순열과 조합은 항상 간단한 것 같으면서 나를 헷갈리게 하였고, 이 참에 정리를 하려고 한다.
백트래킹

순열

서로다른 수에서 뽑아서 정렬하는 경우의 수

정렬이기에 순서가 존재한다.

조합

서로다른 수에서 뽑을수 있는 조합의 수

순서가 중요하지않고 중복이 없다,

---

아래의 코드는 순열,중복순열,조합,중복조합의 기본 형태를 나타내었다.
중요한 것은 이러한 기본코드를 이해해야지 조합이나 순열을 활용해서 문제에 맞게 풀어 낼 수있다는 것이다.
조합을 활용한 풀이는 아래 링크에 있다. 확인해보는 것을 추천한다.

https://dreaming-potato.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv2-%EB%A9%94%EB%89%B4-%EB%A6%AC%EB%89%B4%EC%96%BC

package com.example;

import java.util.*;
public class Main {
    static int n,m ;
    static int[] arr;
    static boolean[] visited;

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

    public 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;
            }
        }
    }
    public 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;
            repeatedPermutation(cnt + 1);
        }
    }

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

    public 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;
            repeatedCombination(cnt+1,i);
        }
    }

}