[JAVA]순열 조합 부분집합

순열 : 서로 다른 n개 원소 중에서 r 개 원소를 뽑아서 줄을 세워 나열하는 것 nPr

순열은 줄을 세워 나열한다고 말한것 처럼 원소의 순서에 따라 서로 다르게 경우의 수로 생각합니다 

예 : {2,1} 와 {1,2}는 서로 다른 경우의 수이다

간단한 예시 :

3명의 학생 A, B, C 중 반장과 부반장을 구하는 경우의 수를 구하라

반장	부반장
A	B
A	C
B	A
B	C
C	A
C	B

 

public class permutation_test { // 반장과 부반장을뽑는 프로그램 
	// 선택하고자 하는 대상 집합.
	static String[] member = new String[] { "A", "B", "C" };
	
	static boolean[] visited = new boolean[3]; //뽑았는지 안뽑았는지 확인하는 boolean
	
	static String [] answer =new String[2];

	public static void main(String[] args) {
		permutation(0);
	}

	// 순열  cnt 는 현재 몇명을 뽑았는지를 뜻한다 
	private static void permutation(int cnt) {
		// 2명 즉 반장과 부반장이 모두 뽑혔으니까 배열을 출력하고 return
		if (cnt == 2) {
			for(int i=0;i<2;i++) {
				System.out.print(answer[i]);
			}
			System.out.println();
			return;
		}
		// 대상 집합을 순회하며 문자를 하나 선택한다.
		for (int i = 0; i < 3; i++) {
			// 이미 answer 에 뽑혀있을경우에는  continue;
			if (visited[i]) {
				continue;
			}
			// 선택하지 않은경우, 선택했다는 표시를 해준다.
			visited[i] = true; //뽑은경우
			answer[cnt]=member[i]; // answer 에 값을 추가 
			permutation(cnt + 1); // 한명을 뽑은것임으로 cnt +1 을해주고 재귀호출
			// 선택을 해제한다.
			visited[i] = false; // 안뽑은경우 
		}
	}
}

결과

 

조합 : 서로 다른 n개의 원소 중에서 r개를 고르는 것 nCr

조합은 순열과 달리 순서에 따라 다른 경우라고 생각하지 않습니다 

예 : {2,1}와 {1,2}는 서로 같은 경우의 수이다

간단한 예시 :

3명의 학생 A, B, C 중 주번 2명을 구하는 경우의 수를 구하라

주번	주번
A	B
A	C
B	C

 

public class combination_test {
static String[] member = new String[] { "A", "B", "C" };
	

	
	static String [] answer =new String[2];

	public static void main(String[] args) {
		combination(0,0);
	}

	//  cnt 는 현재 몇명을 뽑았는지를 뜻한다 
	private static void combination(int cnt ,int start) {
		// 2명의 주번이  모두 뽑혔으니까 배열을 출력하고 return
		if (cnt == 2) {
			for(int i=0;i<2;i++) {
				System.out.print(answer[i]);
			}
			System.out.println();
			return;
		}
		// 대상 집합을 순회하며 문자를 하나 선택한다.
		for (int i = start; i < 3; i++) {
			// 이미 answer 에 뽑혀있을경우에는  continue;
		
			answer[cnt]=member[i]; // answer 에 값을 추가 
			combination(cnt + 1 , i+1); // 한명을 뽑은것임으로 cnt +1 와 i+1을해주고 재귀호출
			
		}
	}

}

결과

 

부분집합 : PowerSet 또는 SubSet이며 원소를 이용해 만들 수 있는 모든 부분집합을 뜻한다 2^n 개

간단한 예시 :

3명의 학생 A, B, C 중 장기자랑에 참가하는 경우의 수를 구하라 

모두 다 참여할 수 도 있고 , 모두 다 참여하지 않을 수도 있다 

{ABC}
{AB}
{AC}
{A}
{BC}
{B}
{C}
{}

 

public class subset_test {
	
static String[] member = new String[] { "A", "B", "C" };
static boolean[] visited = new boolean[3];

	

	public static void main(String[] args) {
		subset(0);
	}

	// 순열  cnt 는 현재 몇명을 뽑았는지를 뜻한다 
	private static void subset(int cnt) {
		// 2명의 주번이  모두 뽑혔으니까 배열을 출력하고 return
		if (cnt == 3) {
			System.out.print("{");
			for(int i=0;i<3;i++) {
				if(visited[i]) {
					System.out.print(member[i]);
				}
			}
			System.out.print("}");
			System.out.println();
			return;
		}
		// 대상 집합을 순회하며 문자를 하나 선택한다.
		visited[cnt]=true;
		subset(cnt+1);
		visited[cnt]=false;
		subset(cnt+1);
		
			
		}
	}

 

결과