[알고리즘] 순열과 조합

알고리즘을 풀이할 때 가장 처음으로 해보아야 하는 것은

브루트 포스(Brute Force), 즉 완전 탐색이다.

 

이러한 완전 탐색을 하기 위해서 필요한 지식 중 한 가지는 바로 순열과 조합이며

이번 게시물에서는 순열과 조합을 다룬다.

 

n가지 물건이 있다고 가정한다면,

 

순열은 n가지 물건에서 r개를 순서를 고려하여 선정하는 것이다.

nPr의 기호로 표현하며 가지 수를 계산한다면

nPr = n(n-1)(n-2)....(n-r+1) 이 된다.

 

조합은 n가지 물건에서 r개를 순서를 고려하지 않고 선정하는 것이며

nCr의 기호로 표현하며 가지수를 계산한다면 

nCr = nPr / r! = n! / r!(n-r)! 이다.

 

이를 코드로 구현하면 다음과 같다.

public class Main {
	static ArrayList<Integer> intList = new ArrayList<>();
	static Stack<Integer> selectedStack = new Stack<>();
	static boolean[] isSelected;
	static int num;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		num = 3;
		for(int i=1; i<=4; i++)
			intList.add(i);
		
		isSelected = new boolean[intList.size()];
		Arrays.fill(isSelected, false);
		
		System.out.println("순열");
		permutation(0);
		
		System.out.println("재귀로 구현한 조합");
		combination(0, 0);
		
		System.out.println("for문으로 구현한 조합");
		combination2(0, 0);
	}
	
	
	static void permutation(int count) {
		int i;
		if(count == num) {
			for(int n : selectedStack)
				System.out.print(n + " ");
			System.out.println();
			
			return;
		}
		
		for(i=0; i<intList.size(); i++) {
			if(!isSelected[i]) {
				isSelected[i] = true;
				selectedStack.push(intList.get(i));
				permutation(count+1);
				isSelected[i] = false;
				selectedStack.pop();
			}
		}
	}
	
	static void combination(int check, int count) {
		if(count == num) {
			for(int n : selectedStack)
				System.out.print(n + " ");
			System.out.println();
			
			return;
		}
		
		if(check >= intList.size())
			return;
		
		selectedStack.push(intList.get(check));
		combination(check+1, count+1);
		selectedStack.pop();
		combination(check+1, count);
	}
	
	static void combination2(int check, int count) {
		int i;
		if(count == num) {
			for(int n : selectedStack)
				System.out.print(n + " ");
			System.out.println();
			
			return;
		}
		
		if(check >= intList.size())
			return;
		
		for(i=check; i<intList.size(); i++) {
			selectedStack.push(intList.get(check));
			combination2(i+1, count+1);
			selectedStack.pop();
		}
	}
}

출력 결과