순열과 조합 그리고 부분집합
1. 순열 (permutation)
간단하게 말하여 N개중 R개를 골라서 순서대로 나열하는것을 의미하는데 여기서 조합과 다른점은 "순서가 존재한다"라는 것이다. 예를 들어 1,2,3 이 적혀있는 숫자카드가 3개존재하는데 이중 3장을 뽑은 경우의 수는 순열의 경우는 [1,2,3] 단 하나 밖에 존재하지 않는다.
서로다른 n개에서 r개를 택하는 순열의 수
nPr=n(n-1)(n-2)...(n-r+1)
public class permutaion {
static int N,R, input[], numbers[];
static boolean [] isSelected;
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
N=sc.nextInt();
R=sc.nextInt();
input=new int[N];
numbers=new int[R];
isSelected=new boolean[N];
for (int i=0; i<N; i++) {
input[i]=sc.nextInt();
}
System.out.println("순열");
perm(0);
}
static void perm(int cnt) {
if(cnt==R) {
System.out.println(Arrays.toString(numbers));
return;
}
for(int i=0; i<N; i++) {
if(isSelected[i])
continue;
numbers[cnt]=input[i];
isSelected[i]=true;
perm(cnt+1);
isSelected[i]=false;
}
}
}2. 조합 (combination)
간단하게 말하여 N개중 R개를 골라서 순서대로 나열하는것을 의미하는데 여기서 순열과 다른점은 "순서에 의미가 없다"라는 것이다. 예를 들어 1,2,3 이 적혀있는 숫자카드가 3개존재하는데 이중 3장을 뽑은 경우의 수는 조합의 경우는 [1,2,3],[1,3,2], [2,1,3],[2,3,1]...[3,2,1] 6가지의 경우가 존재한다.
서로다른 n개에서 r개를 택하는 조합의 수
nCr=n!/r!(n-r)!
public class combination {
static int N,R, input[], numbers[];
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
N=sc.nextInt();
R=sc.nextInt();
input=new int[N];
numbers=new int[R];
for (int i=0; i<N; i++) {
input[i]=sc.nextInt();
}
comb(0,0);
}
static void comb(int cnt, int start) {
if(cnt==R) {
System.out.println(Arrays.toString(numbers));
return;
}
for(int i=start; i<N; i++) {
numbers[cnt]=input[i];
comb(cnt+1, i+1);
}
}
}3. 부분집합 (subset)
부분집합의 개념은 따로 설명하지 않겠다. 갖고있는 원소를 사용하여 만들어낼수있는 집합을 부분집합이라고 이해하면 될 것 같다.
public class subset {
static int N,R, input[], numbers[];
static boolean [] isSelected;
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
N=sc.nextInt();
R=sc.nextInt();
input=new int[N];
numbers=new int[R];
isSelected=new boolean[N];
for (int i=0; i<N; i++) {
input[i]=sc.nextInt();
}
subset(0);
}
static void subset(int cnt) {
if(cnt==N) {
for(int i=0; i<N; i++) {
System.out.print((isSelected[i]? input[i]: "X") +" ");
}
System.out.println();
return;
}
isSelected[cnt]=true;
subset(cnt+1);
isSelected[cnt]=false;
subset(cnt+1);
}
}[추가개념] 중복순열과 중복조합
중복순열: 서로 다른 n개에서 중복이 가능하게 r개를 뽑아서 정렬하는 경우의 수
순열과의 차이점은 같은 원소를 중복해서 뽑는것이 가능하다는것!
public class tip {
public static void permutation(int[] arr, int[] out, int depth, int r){
if(depth == r){
for(int num: out) System.out.print(num);
System.out.println();
return;
}
for(int i=0; i<arr.length; i++){
out[depth] = arr[i];
permutation(arr, out, depth+1, r);
}
}
public static void main(String[] args){
int[] arr = {1, 2, 3};
int r = 2;
permutation(arr, new int[r], 0, r);
}
}- 순열과 유일한 차이가 중복이 가능하다는 것이므로, 순열 코드에서 중복을 방지하기 위해서 사용했던 visited부분을 제거
중복조합: 서로 다른 n개에서 순서 없이, 중복이 가능하게 r개를 뽑는 경우의 수
조합과의 차이점은 마찬가지로 뽑은것을 또 뽑을 수 있다는 점!
public class tip {
public static void combination(int[] arr, int[] out, int start, int depth, int r){
if(depth == r){
for(int num : out) System.out.print(num);
System.out.println();
return;
}
for(int i=start; i<arr.length; i++){
out[depth] = arr[i];
combination(arr, out, i, depth+1, r);
}
}
public static void main(String[] args){
int[] arr = {1, 2, 3};
int r = 2;
combination(arr, new int[r], 0, 0, r);
}
}- 조합과 유일한 차이점은 중복이 가능하다는 것이므로, 조합 코드에서 중복을 체크하기 위해 사용한 visited를 사용하는 부분을 제거
- 또한 현재 선택한 원소보다 뒤의 것만 선택 가능하지 않고, 현재 선택한 원소를 포함하여 그 뒤의 것들을 선택 가능한 것이므로 재귀 호출에서 start로 i+1을 넘기던 조합 코드에서 그냥 i를 넘기는 것으로 수정
- 조합과는 다르게 중복이 가능하기 때문에 선택한 원소를 저장하는 배열이 필요
나태지옥