[Algorithm] 순열(Permutation)과 조합(Combination) JAVA로 구현하기 (순열, 중복순열, 조합, 중복조합)

 

순열(n​Pr)​

import java.util.*;
public class Main {
	
	static int n, r;
	static int arr[] = {1,2,3,4,5,6,7,8,9};
	static int result[] = new int[10];
	static boolean visit[] = new boolean[11];
	
	public static void permutation(int cnt) {
		if(cnt == r) {
			for (int i = 0; i < r; i++) {
				System.out.print(result[i] + " ");
			}
			System.out.println();
		}else {
			for (int i = 0; i < n; i++) {
				if(visit[i]) continue;
				
				result[cnt] = arr[i];
				visit[i] = true;
				permutation(cnt+1);
				visit[i] = false;
			}
		}
	}
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt(); 
		r = sc.nextInt();
		
		permutation(0);
		
	}
}

 

 

중복 순열(nΠr)

import java.util.*;
public class Main {
	
	static int n, r;
	static int arr[] = {1,2,3,4,5,6,7,8,9};
	static int result[] = new int[10];
	
	public static void permutation_r(int cnt) {
		if(cnt == r) {
			for (int i = 0; i < r; i++) {
				System.out.print(result[i] + " ");
			}
			System.out.println();
		}else {
			for (int i = 0; i < n; i++) {
				result[cnt] = arr[i];
				permutation_r(cnt+1);
			}
		}
	}
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt(); 
		r = sc.nextInt();
		
		permutation_r(0);
		
	}
}

 

 

조합(nCr)

import java.util.*;
public class Main {
	
	static int n, r;
	static int arr[] = {1,2,3,4,5,6,7,8,9};
	static int result[] = new int[10];
	static boolean visit[] = new boolean[10];
	
	public static void combination(int idx, int cnt) {
		if(cnt == r) {
			for (int i = 0; i < r; i++) {
				System.out.print(result[i]+" ");
			}
			System.out.println();
		}else {
			for (int i = idx; i < n; i++) {
				if(visit[i]) continue;
				
				result[cnt] = arr[i];
				visit[i] = true;
				combination(i,cnt+1);
				visit[i] = false;
			}
		}
	}
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt(); 
		r = sc.nextInt();
		
		combination(0,0);
		
	}
}

 

 

중복 조합(nHr)

import java.util.*;
public class Main {
	
	static int n, r;
	static int arr[] = {1,2,3,4,5,6,7,8,9};
	static int result[] = new int[10];
	
	public static void combination(int idx, int cnt) {
		if(cnt == r) {
			for (int i = 0; i < r; i++) {
				System.out.print(result[i]+" ");
			}
			System.out.println();
		}else {
			for (int i = idx; i < n; i++) {
				result[cnt] = arr[i];
				combination(i,cnt+1);
			}
		}
	}
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt(); 
		r = sc.nextInt();
		
		combination(0,0);
	}
}

 

 

 

 

+ 뜬금포

조합 구현하면서 불현듯이 어릴때 했었던 메이플스토리의 고전 조합 문제가 떠올랐습니다. (ㅎㅎ;;;;)

루디브리엄 파티퀘스트인데 예전에 메이플 하셨던 분들이라면 다들 아실거에요! 

조합 문제라 1번자리 사람은 계속 가만히 있고 마지막 끝자리에 있는사람만 발바닥에 불나게 뛰어다녔던 경험이 있네요 ㅋㅋㅋ

사람은 6명이고 번호박스는 9개! 경우의 수는 얼마나 될까요?

어릴때는 그냥 무지성으로 하나하나씩 해보면서 보통은 5분을 안넘기고 깼었던걸로 기억하는데....

경우의 수가 84밖에 되지 않는군요! 그정도면 5분내로 깨기가 가능할 것 같습니다 ㅎㅎ

 

왜 그때 루디브리엄 파티퀘스트 인원을 꼭 6명으로 맞춰야했는지...
10년이 지나 이제서야 개발자의 의도를 조금이나마 알게된 것 같습니다.