[알고리즘] 순열/중복순열/조합/중복조합/멱집합

박채은·2022년 11월 28일

Algorithm

목록 보기

4/10

모든 코드는 ArrayList<Integer[]>인 result를 반환하도록 구현하였다.
result 내에는 n과 r이 주어졌을 때, 모든 경우를 저장한다.

(저장하지 않고, 경우를 그대로 출력하는 것이 더 쉽지만, 재귀의 flow에 익숙해질 수 있게 result를 return하는 코드를 짜봤다.)

순열

DFS(재귀)

인자

ArrayList<Integer[]> result : 전체 경우의 수를 저장할 ArrayList
arr[] : 순열을 실행할 배열(arr.length = n)
r : n 개 중 뽑힐 갯수
out[] : 뽑힌 r개의 값을 저장하는 배열 (하나의 경우만 저장)
visited[] : 중복해서 뽑지 않기 위해 방문했는지를 체크하는 배열
depth : DFS의 깊이, out[]에 들어간 숫자의 길이

과정

중복을 허용하지 않으므로, 뽑은 적 없는 값만 배열에 추가
- 각 경우들은 ArrayList<Integer[]>에 저장되어야 하므로, out[] 배열을 깊은 복사해서 새로운 배열(newArr)로 만든 후, ArrayList에 추가해야 한다.
out[]에 들어간 숫자의 길이인 depth가 뽑으려는 갯수인 r과 같아지면, 하나의 경우가 완성되는 것이므로 result에 추가하고 return한다.
하나의 경우를 완성하면, 백트래킹되어 visited[i] = false를 해준다.
- 해당 arr[i]가 다른 경우에도 사용될 수 있으므로

public static void main(String[] args) {
    Integer[] arr = {1, 2, 3, 4, 5};
    int r = 3;

    ArrayList<Integer[]> output = permutation(new ArrayList<>(), arr, new Integer[r], new boolean[arr.length], 0, r);
    output.forEach(e -> System.out.println(Arrays.toString(e)));
}

public ArrayList<Integer[]> permutation(ArrayList<Integer[]> result, Integer[] arr, Integer[] out, boolean[] visited, int depth, int r) {
     if (depth == r) {
          result.add(out);
          return result;
     }
     for (int i = 0; i < arr.length; i++) {
          if (!visited[i]) {
              visited[i] = true;
              Integer[] newArr = Arrays.copyOf(out, out.length);
              newArr[depth] = arr[i];
              result = permutation(result, arr, newArr, visited, depth + 1, r);
              visited[i] = false;
          }
      }
      return result;
}

문제

코플릿 - 새로운 치킨 소스 레시피

중복 순열

중복 순열은 중복을 체크하지 않는다는 것만 제외하곤, 순열과 동일하다.

public static void main(String[] args) {
    Integer[] arr = {1, 2, 3, 4, 5};
    int r = 3;

    ArrayList<Integer[]> output = permutation(new ArrayList<>(), arr, new Integer[r], 0, r);
    output.forEach(e -> System.out.println(Arrays.toString(e)));
}

public ArrayList<Integer[]> permutation(ArrayList<Integer[]> result, Integer[] arr, Integer[] out, int depth, int r) 
	if (depth == r) {
       result.add(out);
       return result;
    }
    for (int i = 0; i < arr.length; i++) {
        Integer[] newArr = Arrays.copyOf(out, out.length);
        newArr[depth] = arr[i];
        result = permutation(result, arr, newArr, depth + 1, r);
     }
     return result;
}

문제

코플릿 - 가위바위보

조합

public static void main(String[] args){
    Integer[] arr = {1, 2, 3,4,5};
    int r = 4;

    ArrayList<Integer[]> output = combination(new ArrayList<>(), arr, new Integer[r], 0, 0, r);
    output.forEach(e -> System.out.println(Arrays.toString(e)));
}

public ArrayList<Integer[]> combination(ArrayList<Integer[]> result, Integer[] arr, Integer[] out, int start, int depth, int r){
    if(depth == r){
        result.add(out);
        return result;
    }
    
    for(int i=start; i<arr.length; i++){
        Integer[] newArr = Arrays.copyOf(out, out.length);
        newArr[depth] = arr[i];
        result = combination(result, arr, newArr, i+1, depth+1, r);
    }
    return result;
}