순열, 조합, 부분집합

교육 초반에 쓰다가 한동안 보이지 않았었는데, dfs나 bfs와 결합된 알고리즘에서 많이 사용되어 잊어버리지 않기 위해 다시 정리하기로 했다

순열(Permutation = nPr)

= n*n-1*n-2* ... * n-r+2 * n-r+1

= n부터 r개만큼 곱하기

 

- 서로 다른 n개의 수들 중 r개를 순서를 맞춰 뽑음

- 출발지, 도착지를 선택하면 이동 경비를 최소로 사용하면서 모든 도시를 여행하는 경우

- 릴레이 계주 선수 4명 중 3명을 뽑는다 = ₄P₃

 

예시 코드

- input, numbers, isSelected 사용

	int N = 4; // 주어진 N개의 수
	int R = 3; // 뽑으려고 하는 수 R
	
	int[] input = new int[N]; // input에 N개의 숫자 넣기
	int[] numbers = new int[R]; // numbers에 R개의 숫자 뽑아서 출력
	boolean[] isSelected = new boolean[N]; // 숫자를 사용했는지 안 했는지 확인
	
	for (int i = 0; i < N; i++) {
		input[i] = Integer.parseInt();
	}

	public static void Permutation(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;
			Permutation(cnt+1);
			isSelected[i] = false;
		}
		
	}

 

조합(Conbination = nCr)

= n! / (n-r)!r!

= n부터 r개 / 1부터 r까지

 

- 서로 다른 n개의 수들 중 r개를 순서 없이 뽑음

- 여행 경비 70만 원 안에서 최대 비용으로 여행지 세 곳을 여행하는 경우

- 달리기 선수 4명 중 3명을 뽑는다 = ₄C₃

 

예시 코드

- input, numbers, start 사용

	int N = 4; // 주어진 N개의 수
	int R = 3; // 뽑으려고 하는 수 R
	
	int[] input = new int[N]; // input에 N개의 숫자 넣기
	int[] numbers = new int[R]; // numbers에 R개의 숫자 뽑아서 출력
	
	for (int i = 0; i < N; i++) {
		input[i] = Integer.parseInt();
	}

	public static void Combination(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];
			Combination(cnt+1, i+1); // 다음 자리는 현재 뽑은 i의 다음 수부터
		}
		
	}

 

부분집합(Subset = 2^n)

= n! / (n-r)!r!

= n부터 r개 / 1부터 r까지

 

- 서로 다른 n개의 수를 순서 없이 뽑을 수 있는 모든 경우의 수

- 가방 무게를 초과하지 않으면서 최대 이익을 찾는 경우 => 부분집합 중 가장 이익이 큰 값 선택

 

예시 코드

- input, isSelected 사용(numbers 사용 X)

	int N = 4; // 주어진 N개의 수
	
	int[] input = new int[N]; // input에 N개의 숫자 넣기
	
	for (int i = 0; i < N; i++) {
		input[i] = Integer.parseInt();
	}

	public 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[i] = true;
		Subset(cnt+1);
        // 현재 원소를 미선택
		isSelected[i] = false;
		Subset(cnt+1);
	}