순열과 조합
Last updated
Was this helpful?
Last updated
Was this helpful?
서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation) 이라고 한다.
중복을 허용하면 중복 순열이라고 한다.
//4개의 원소 중에서 2개를 뽑는 순열
package practice.algorithm.math;
public class Permutation {
public static void main(String[] args) {
int[] input = {1, 2, 3, 4};
int r = 2;
int[] output = new int[r];
boolean[] visited = new boolean[input.length];
permutation(input, visited, output, 0, input.length, r);
}
private static void permutation(int[] input, boolean[] visited, int[] output, int depth, int inputLength, int r) {
if (depth == r) {
printOutput(output, r);
return;
}
for (int i = 0; i < inputLength; i++) {
if (!visited[i]) {
visited[i] = true;
output[depth] = input[i];
permutation(input, visited, output, depth+1, inputLength, r);
visited[i] = false;
}
}
}
private static void printOutput(int[] output, int r) {
for (int num : output) {
System.out.print(num + " ");
}
System.out.println();
}
}
중복을 제거하기 위한 visited 배열 제외
package practice.algorithm.math;
public class PermutationRepeated {
private static int[] input;
private static int[] output;
private static int r;
public static void main(String[] args) {
input = new int[]{1, 2, 3, 4};
r = 2;
output = new int[r];
permutation(0);
}
private static void permutation(int depth) {
if (depth == r) {
printOutput(output);
return;
}
for (int i = 0; i < input.length; i++) {
output[depth] = input[i];
permutation(depth+1);
}
}
private static void printOutput(int[] output) {
for (int num : output) {
System.out.print(num + " ");
}
System.out.println();
}
}
서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관없이 뽑는 것을 말한다.
중복을 허용하면 중복조합이라고 한다.
package practice.algorithm.math;
import java.util.Arrays;
public class Combination {
private static int[] input;
private static int[] output;
private static int r;
public static void main(String[] args) {
input = new int[]{1, 2, 3, 4};
r = 2;
output = new int[r];
combination(0, 0);
}
private static void combination(int depth, int start) {
if (depth == r) {
System.out.println(Arrays.toString(output));
return;
}
for (int i = start; i < input.length; i++) {
output[depth] = input[i];
combination(depth+1, i+1); //오름차순으로 구하기 때문에 중복체크를 안해도 된다.
}
}
}
package practice.algorithm.math;
import java.util.Arrays;
public class CombinationRepeated {
private static int[] input;
private static int[] output;
private static int r;
public static void main(String[] args) {
input = new int[]{1, 2, 3, 4};
r = 2;
output = new int[r];
combination(0, 0);
}
private static void combination(int depth, int start) {
if (depth == r) {
System.out.println(Arrays.toString(output));
return;
}
for (int i = start; i < input.length; i++) {
output[depth] = input[i];
combination(depth+1, i); //중복을 허용하므로, 같은 수 반복
}
}
}