[Algorithm] 순열, 조합 구현

순열 : 서로 다른 n개의 수에서 r개를 뽑아서 정렬하는 경우의 수( nPr 로 표현된다.)

• 순열은 순서를 생각해서 뽑아야 한다. 예를 들어 {1,2,3,4,5} 중에서 3개의 수를 뽑아야 하는 경우 {2,3,4}와 {2,4,3} 은 다른 경우의 수로 카운트된다.
• 재귀를 통해 구현할 수 있다. 순열을 구현하기 위해서는 함수 안에서 현재 수를 뽑고 다음수를 뽑기 위해 재귀함수를 호출한다.  
• 특히, 중복순열과는 다르게 순열은 중복해서 수를 뽑을 수 없기 때문에, 현재 수를 뽑았는지를 확인하기 위해 boolean배열을 사용한다.

public class PermutationTest {
	private static int N;//총 개수
	private static int R;//뽑을 개수
	private static boolean[] isSelected;//해당 수를 뽑았는지 여부 확인
	private static int[] numbers;
	private static int totalCount;
	
	public static void main(String[] args) {
	
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();//총 개수
		R = sc.nextInt();//뽑을 개수
		
		numbers = new int[R];
		isSelected = new boolean[N+1];
	
		permutation(0);
		
		System.out.println("총 경우의 수 : " + totalCount);
	}//end of main
	
	
	
	/**
	 * @param cnt 직전까지 뽑은 순열에 포함된 수의 개수
	 * cnt + 1번째 해당하는 순열에 포함될 수를 뽑기
	 */
	public static void permutation(int cnt) {
		if(cnt == R) {//탈출 조건 : R개의 수를 전부 뽑은 경우
			totalCount++;
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		//가능한 모든 수에 대해 시도
		for (int i = 1; i <= N; i++) {
			//시도한 수가 선택되었는지 판단함
			if(isSelected[i]) continue;
			
			//선택되지 않았다면 현재 수를 사용함
			numbers[cnt] = i;
			isSelected[i] = true;
			
			//다음 수를 뽑으러 가기
			permutation(cnt+1);
			
			//사용했던 수에 대한 선택 되돌리기
			isSelected[i] = false;
		}
	}
	
}//end of Class

 

출력결과

 

---

조합 :  nCr이라고 표현되며,  n개의 입력받은 수 중 r개를 모두 뽑아 순서없이 나열하는 것(1<=r<=n)

 

• 예를 들어, {1,2,3,4,5}에서 3개를 뽑아야 하는 경우에 순열과는 다르게 {2,3,4}와 {2,4,3}을 같은 경우의 수라고 취급합니다.  
• 구현 : 조합의 경우에는 순서에 상관없이 수를 뽑아야 하므로 {2,3,4}와 {2,4,3} 같은 경우에 두 경우에 대해 전부 카운트(+2)하면 안됩니다. 따라서, 반복문 안에서 start부터 시작하여 이미 처리한 수에 대해 중복되게 사용하는 경우를 방지합니다. 

public class CombinationTest {
	private static int N;//총 개수
	private static int R;//뽑을 개수
	private static boolean[] isSelected;
	private static int[] numbers;
	private static int totalCount;
	private static int[] input;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		R = sc.nextInt();
		
		input = new int[N];//전체 n개 배열
		numbers = new int[R];//전체 r개 배열
		
		for (int i = 0; i < N; i++) {
			input[i] = sc.nextInt();
		}
		
		combination(0,0);
		
		System.out.println("총 경우의 수 : " + totalCount);
	} 
	
	
	/**
	 * @param cnt 직전까지 뽑은 조합에 포함된 수의 개수
	 * @param start 시도할 수의 시작 위치
	 */
	private static void combination(int cnt, int start) {
		if(cnt == R) {
			totalCount++;
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		//start부터 처리하여 수를 중복되게 뽑는 경우를 방지하며, 순서가 다른 조합 추출 방지
		for (int i = start; i < N; i++) {
			//앞쪽에서 선택되지 않았다면 현재 수를 선택함
			numbers[cnt] = input[i];
			//다음 수를 뽑으러 가기
			combination(cnt+1, i+1);
		}
		
	}
	
}

 

출력결과