Java 순열 구현
1. Permutation 1 (idx 활용)
public class Permutation1 {
static int N; // 원소의 개수
static int R; // 뽑을 개수
static int[] data; // 입력받은 data
static int[] numbers; // 순열을 담을 배열
public static void main(String[] args) {
data = new int[] {1, 2, 3};
N = data.length;
R = data.length;
numbers = new int[R];
permutation(0);
}
public static void permutation(int idx) {
if(idx == R) {
System.out.println(Arrays.toString(numbers));
}
top:
for(int i = 0; i < N; i++) {
// 중복 검사
for(int j = 0; j < idx; j++) {
if(numbers[j] == data[i]) {
// 중복된 경우
continue top;
}
}
numbers[idx] = data[i];
permutation(idx + 1);
}
}
}
[출력 결과]

2. Permutation 1 (flag 활용)
public class Permutation2 {
static int N; // 원소의 개수
static int R; // 뽑을 개수
static int[] data; // 입력받은 data
static int[] numbers; // 순열을 담을 배열
static boolean[] isSelected; // 중복을 체크하기 위한 배열
public static void main(String[] args) {
data = new int[] {1, 2, 3};
N = data.length;
R = data.length;
numbers = new int[R];
isSelected = new boolean[N];
permutation(0);
}
public static void permutation(int idx) {
if(idx == R) {
System.out.println(Arrays.toString(numbers));
}
for(int i = 0; i < N; i++) {
// 중복 검사
if(isSelected[i]) continue;
numbers[idx] = data[i];
isSelected[i] = true;
permutation(idx+1);
isSelected[i] = false;
}
}
}
[출력 결과]

3. bitmask 활용
public class Permutation3 {
static int N; // 원소의 개수
static int R; // 뽑을 개수
static int[] data; // 입력받은 data
static int[] numbers; // 순열을 담을 배열
/**
*
* @param idx 뽑을 원소의 위치
* @param flag 원소 중복 체크를 위한 flag
*/
public static void main(String[] args) {
data = new int[] {1, 2, 3};
N = data.length;
R = data.length;
numbers = new int[R];
permutation(0, 0);
}
public static void permutation(int idx, int flag) {
if(idx == R) {
System.out.println(Arrays.toString(numbers));
return ;
}
for(int i = 0; i < N; i++) {
// 중복 검사
if((flag & 1 << i) != 0) continue;
numbers[idx] = data[i];
permutation(idx + 1, flag | 1 << i);
}
}
}
[실행 결과]

4. swap
static int[] data = {1, 2, 3, 4, 5};
static int cnt = 0;
public static void main(String[] args) {
perm(0);
System.out.println(cnt);
}
public static void perm(int depth) {
// 뽑고 싶은 수만큼 뽑음
if(depth == 3) {
cnt++;
System.out.println(Arrays.toString(data));
return;
}
for(int i = depth; i < data.length; i++) {
swap(i, depth);
perm(depth + 1);
swap(depth, i);
}
}
public static void swap(int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}

Java 조합 구현
<1>
static int[] selected = new int[2];
static int cnt = 0;
public static void main(String[] args) {
combi(1, 0);
System.out.println(cnt);
}
public static void combi(int start, int depth){
if(depth == 2){
cnt++;
System.out.println(Arrays.toString(selected));
return;
}
for(int i = start; i <= 4; i++){
selected[depth] = i;
combi(i + 1, depth + 1);
}
}

Java 부분 집합 구현
static int[] data = {1, 2, 3, 4};
static boolean[] selected = new boolean[4];
static int cnt = 0;
public static void main(String[] args) {
subset(0);
System.out.println(cnt);
}
public static void subset(int depth) {
// 뽑고 싶은 수만큼 뽑음
if(depth == 4) {
cnt++;
for(int i = 0; i < 4; i++) {
if(selected[i]) {
System.out.print(data[i] + " ");
}
}
System.out.println();
return;
}
selected[depth] = true;
subset(depth + 1);
selected[depth] = false;
subset(depth + 1);
}

'Programming Language > JAVA' 카테고리의 다른 글
| [프로그래머스] 순위검색 - 2021 KAKAO BLIND RECRUITMENT (0) | 2024.04.08 |
|---|---|
| 'The package java.sql is not accessible' 해결 (0) | 2024.03.14 |
| [Java] BFS vs DFS (0) | 2024.02.20 |
| [Java] Call by Value, Call by Reference (0) | 2024.01.18 |
| [Java] 자바 JVM 내부 구조 & 메모리 구조 (1) | 2024.01.16 |