[JAVA] 순열, 중복순열, 조합, 중복 조합 구현

순열 (Permutation)

• 서로 다른 것들 중 몇 개를 뽑아서 한줄로 나열하는 것

• 서로 다른 n개중 r개를 택하는 순열 == nPr

• nPn == n!

• n>12 인 경우 시간 복잡도가 폭발적으로 증가

• 순열 자바 구현

import java.util.Arrays;

public class permutation {

	static int arr[]; 
	static boolean isSelected[];
	static int numbers[];
	static int n = 5;
	static int r = 5;
	
	public static void main(String[] args) {
		arr= new int[]{1,2,3,4,5};
		isSelected = new boolean[r];
		numbers = new int[r];
		
		per(0);
	}
	
	public static void per(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] = arr[i];
			isSelected[i] = true;
			per(cnt+1);
			isSelected[i] = false;
		}
	}

}

중복 순열 (Permutation with repetition)

• 서로 다른 n개의 원소 중에서 중복을 허용하여 r개를 뽑아서 한 줄로 나열하는 것

• n^r

• 중복 순열 자바 구현

import java.util.Arrays;

public class PermutationWithRepetition {

	static int arr[];
	static int numbers[];
	static int n = 5;
	static int r = 3;
	public static void main(String[] args) {
		
		arr = new int[] {1,2,3,4,5};
		numbers = new int[r];
		
		perRep(0);
	}
	
	public static void perRep(int cnt) {
		if(cnt == r) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for(int i=0;i<n;i++) {
			numbers[cnt] = arr[i];
			perRep(cnt+1);
		}
	}

}

조합 (Combination)

• 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것

• nCr = n! / ((n-r)! * r!)

• nCr = n-1Cr-1 + n-1Cr

• nC0 = 1

• 조합 자바 구현

import java.util.Arrays;

public class Combination {

	static int arr[];
	static int numbers[];
	static int n = 5;
	static int r = 3;
	public static void main(String[] args) {
		
		arr = new int[] {1,2,3,4,5};
		numbers = new int[r];
		
		combi(0,0);
	}

	
	public static void combi(int start, int cnt) {
		if(cnt == r) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for(int i=start;i<n;i++) {
			numbers[cnt] = arr[i];
			combi(i+1,cnt+1);
		}
	}
}

중복 조합

• 서로 다른 n개의 원소 중 r개를 순서 없이 중복 가능하게 골라낸 것

• nHr = n+r-1Cr

• 중복 조합 자바 구현

import java.util.Arrays;

public class CombinationWithRepetition {

	static int arr[];
	static int numbers[];
	static int n = 3;
	static int r = 4;
	public static void main(String[] args) {

		arr = new int[] {1,2,3};
		numbers = new int[r];
		
		comRep(0);
	}
	
	public static void comRep(int cnt) {
		if(cnt == r) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for(int i=0;i<n;i++) {
			numbers[cnt] = arr[i];
			comRep(cnt+1);
		}
	}

}