순열, 조합 - Brute Force

순열

Brute Force시 경우의 수가 순열 또는 조합 형태로 나타날 수 있다.

아래는 N개의 수(1~N)에서 M개의 순열을 출력하는 코드이다.

import java.util.*;
import java.io.*;

public class Main {
	static int N, M;
	static boolean[] select;
	static LinkedList<Integer> numbers = new LinkedList<>();
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        select = new boolean[N+1];
        f();
    }

    static void f() {
        if(numbers.size() == M) {
            for(int num : numbers) { System.out.print(num); System.out.print(" "); }
            System.out.println();
            return;
        }

        for(int i=1; i<=N; i++) {
        	if(select[i]) continue;
        	select[i] = true;
            numbers.add(i);
            f();
            numbers.remove(numbers.size()-1);
            select[i] = false;
        }
    }
}

조합

아래는 N개의 수(1~N)에서 M개의 조합을 출력하는 코드이다. 기존 순열의 답을 오름차순으로 만들면 중복을 제거해 조합이 된다.

import java.util.*;
import java.io.*;

public class Main {
	static int N, M;
	static LinkedList<Integer> numbers;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        numbers = new LinkedList<>();
        f(1);
    }

    static void f(int start) {
        if(numbers.size() == M) {
            for(int num : numbers) { System.out.print(num); System.out.print(" "); }
            System.out.println();
            return;
        }

        for(int i=start; i<=N; i++) {
            numbers.add(i);
            f(i+1);
            numbers.remove(numbers.size()-1);
        }
    }
}

중복 순열

아래는 N개의 수(1~N)에서 M개의 중복 순열을 출력하는 코드이다. 중복 순열이기에 M이 N보다 커질 수 있다. 위에서는 뽑은 수를 리스트에 저장했지만 여기서는 배열에 저장해 보았다.

import java.util.*;
import java.io.*;

public class Main {
	static int N, M;
	static int[] numbers;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        numbers = new int[M];
        f(0);
    }

    /***
     * @param cnt - 현재 뽑은 개수
     */
    static void f(int cnt) {
        if(cnt == M) {
            for(int num : numbers) { System.out.print(num); System.out.print(" "); }
            System.out.println();
            return;
        }

        for(int i=1; i<=N; i++) {
            numbers[cnt] = i;
            f(cnt+1);
        }
    }
}

중복 조합

아래는 N개의 수(1~N)에서 M개의 중복 조합을 출력하는 코드이다. 중복 조합이기에 M이 N보다 커질 수 있다. 단순히 위에 조합 코드에서 오름차순으로 뽑되, 앞 재귀함수가 뽑은 수부터 뽑도록 허용하면 된다.

import java.util.*;
import java.io.*;

public class Main {
	static int N, M;
	static int[] numbers;
	static int count = 0;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        numbers = new int[M];
        f(0, 1);
    }

    /***
     * @param cnt - 현재 뽑은 개수
     * @param start - 뽑기 시작하는 원소
     */
    static void f(int cnt, int start) {
        if(cnt == M) {
            for(int num : numbers) { System.out.print(num); System.out.print(" "); }
            System.out.println();
            count++;
            return;
        }

        for(int i=start; i<=N; i++) {
            numbers[cnt] = i;
            f(cnt+1, i);
        }
    }
}

모든 부분 집합

모든 경우의 수를 탐색하기 위해 모든 부분 집합을 구하고 각 부분 집합에 알고리즘을 적용해야 하는 문제가 있다. 집합 X가 있을 때, 집합 X의 모든 부분 집합(파워셋)을 구해보자. (집합 X는 n개의 원소를 가지고 있다.) 집합 X의 각 원소에 대해서 선택, 선택하지 않음 하는 2개의 경우를 만들면 총 2ⁿ개의 모든 부분 집합을 구할 수 있다.

 

위 과정을 통해 모든 부분 집합을 구하는 과정 nC₀, nC₁, ... nCn이 자연스럽게 수행된다.

 

아래는 집합 X(numbers)에 들어갈 N개의 수를 입력받고 집합 X의 모든 부분 집합을 출력하는 코드이다.

import java.util.*;
import java.io.*;

public class powerSetTest {

	static int N;
	static int[] numbers;
	static boolean[] selected;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		numbers = new int[N];
		selected = new boolean[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) numbers[i] = Integer.parseInt(st.nextToken());
		
		powerSet(0);
	}
	
	/***
	 * @param idx - 현재 선택할 원소의 인덱스
	 */
	static void powerSet(int idx) {
		if(idx == N) {
			//하나의 부분 집합 완성, 출력 -> 선택된 원소들을 출력
			boolean isEmptySet = true;
			for(int i=0; i<N; i++) {
				if(selected[i]) {
					System.out.print(numbers[i] + " ");
					isEmptySet = false;
				}
			}
			
			//공집합의 경우 아무것도 출력되지 않으므로 아래 내용 출력
			if(isEmptySet) System.out.print("∅");
			
			System.out.println();
			return;
		}
		
		//선택 X
		selected[idx] = false;
		
		//다음으로 넘김
		powerSet(idx + 1);
		
		//선택
		selected[idx] = true;
		
		//다음으로 넘김
		powerSet(idx + 1);
	}
}

추가적으로 부분 집합을 n개의 비트열로 표현할 수 있다. 쉽게 말해 집합 {3, 4, 5}이 있을 때 부분 집합을 000~111로 표현할 수 있다. 즉 { ∅ }은 000으로 {3, 4, 5}은 111로 {3}은 001로 표현할 수 있다. 이렇게 부분집합을 비트열로 보면 한 번의 일차원의 for문으로 모든 부분 집합을 만들고 각 부분 집합에 대해 알고리즘을 적용해 볼 수 있다. 위의 코드에서 부분집합을 비트열로 표현한 코드는 아래와 같다.

import java.util.*;
import java.io.*;

public class powerSetTest {

    static int N;
    static int[] numbers;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        numbers = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) numbers[i] = Integer.parseInt(st.nextToken());

        //모든 부분 집합 순회(subset = 0 ~ 2ⁿ-1)
        for(int subset=0; subset < (1<<N); subset++) {
            //하나의 부분 집합 완성 -> 출력

            //공집합의 경우 ∅ 출력
            if(subset == 0) System.out.print("∅");

            //부분 집합에 포함된 원소들 출력(i번째 비트가 1이면 numbers[i]는 부분집합에 포함됨)
            for(int i=0; i<N; i++) {
                //i번째 비트가 1인지 확인
                if((subset & (1<<i)) > 0) System.out.print(numbers[i] + " ");
            }

            System.out.println();
        }
    }
}