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