Java

자바 순열, 조합 구하기 (파이썬 itertools 라이브러리)

Karla Ko 2024. 3. 12. 13:21
728x90
  • 자바는 파이썬의 itertools 라이브러리 같은 내장함수로 순열, 조합이 없어 직접 구현해야함
  • n개중에 r개 선택한다는 가정
  • Depth를 r만큼 재귀

 

변수
int n, r : n개 중 r개를 뽑음
 int[] now : 현재 저장한 list값 인덱스
 List<List<String>> result : 결과값
 boolean[] visited : 순열 방문 여부

 

순열

public static void permutation(List<String> list, int depth) {
    if (depth == r) {
        List<String> temp = new ArrayList<>();
        for (int i = 0; i < now.length; i++) {
            temp.add(list.get(now[i]));
        }
        result.add(temp);
        return;
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            now[depth] = i;
            permutation(list, depth + 1);
            visited[i] = false;
        }
    }
}

 

중복 순열

public static void permutationWithRepetition(List<String> list, int depth) {
    if (depth == r) {
        List<String> temp = new ArrayList<>();
        for (int i = 0; i < now.length; i++) {
            temp.add(list.get(now[i]));
        }
        result.add(temp);
        return;
    }
    for (int i = 0; i < n; i++) {
        now[depth] = i;
        permutationWithRepetition(list, depth + 1);
    }
}

 

조합

    public static void combination(List<String> list, int depth, int index, int target) {
        if (depth == r) {
            List<String> temp = new ArrayList<>();
            for (int i = 0; i < now.length; i++) {
                temp.add(list.get(now[i]));
            }
            result.add(temp);
            return;
        }
        if (target == n) return;

        now[index] = target;
        combination(list, depth + 1, index + 1, target + 1);
        combination(list, depth, index, target + 1);
    }

 

중복 조합

public static void combinationWithRepetition(List<String> list, int depth, int index) {
    if (depth == r) {
        List<String> temp = new ArrayList<>();
        for (int i = 0; i < now.length; i++) {
            temp.add(list.get(now[i]));
        }
        result.add(temp);
        return;
    }
    for (int i = index; i < n; i++) {
        now[depth] = i;
        combinationWithRepetition(list, depth + 1, i);
    }
}

 

메인

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

    public static int n, r;
    private static int[] now;
    private static boolean[] visited;
    private static List<List<String>> result;

    public static void main(String[] args) {

        List<String> list = Arrays.asList("1", "2", "3");

        n = list.size();
        r = 2;
        now = new int[r];
        visited = new boolean[n];
        result = new ArrayList<>();

        combination(list, 0, 0, 0);
        System.out.println(result);

        combinationWithRepetition(list, 0, 0);
        System.out.println(result);

        permutation(list, 0);
        System.out.println(result);

        permutationWithRepetition(list, 0);
        System.out.println(result);

    }

    public static void permutation(List<String> list, int depth) {
        if (depth == r) {
            List<String> temp = new ArrayList<>();
            for (int i = 0; i < now.length; i++) {
                temp.add(list.get(now[i]));
            }
            result.add(temp);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                now[depth] = i;
                permutation(list, depth + 1);
                visited[i] = false;
            }
        }
    }

    public static void permutationWithRepetition(List<String> list, int depth) {
        if (depth == r) {
            List<String> temp = new ArrayList<>();
            for (int i = 0; i < now.length; i++) {
                temp.add(list.get(now[i]));
            }
            result.add(temp);
            return;
        }
        for (int i = 0; i < n; i++) {
            now[depth] = i;
            permutationWithRepetition(list, depth + 1);
        }
    }
  public static void combination(List<String> list, int depth, int index, int target) {
        if (depth == r) {
            List<String> temp = new ArrayList<>();
            for (int i = 0; i < now.length; i++) {
                temp.add(list.get(now[i]));
            }
            result.add(temp);
            return;
        }
        if (target == n) return;

        now[index] = target;
        combination(list, depth + 1, index + 1, target + 1);
        combination(list, depth, index, target + 1);
    }


    public static void combinationWithRepetition(List<String> list, int depth, int index) {
        if (depth == r) {
            List<String> temp = new ArrayList<>();
            for (int i = 0; i < now.length; i++) {
                temp.add(list.get(now[i]));
            }
            result.add(temp);
            return;
        }
        for (int i = index; i < n; i++) {
            now[depth] = i;
            combinationWithRepetition(list, depth + 1, i);
        }
    }
}

 

 

 

 

728x90