순열, 조합, 부분집합 in JAVA

순열

순열이란 n개의 원소에서 r개의 원소를 *순서에 상관 있이* 뽑는 경우의 수를 의미한다. 

공식 : nPr

ex) 5종류의 음식 중에 2명이 각자 먹을 음식을 시키는 경우의 수(이때 음식을 중복으로 주문하면 안된다.)

 5!/(5-2)!

코드 

package permu;

import java.util.Arrays;

public class sunyul {
	static String arr[] = {"햄버거","피자","떡뽂이","샌드위치","김치찌개"};
	static boolean visit[];
	static String result[];
	static int N = 2; // 고르는 개수 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//5가지 메뉴중 2가지 골라야함 
		visit = new boolean[5];
		result = new String[2]; // 시킨 메뉴 저장 
		back(0);
	
	}
	private static void back(int def) {
		// TODO Auto-generated method stub
		if(def==N) {//두가지 메뉴를 다 골랐다면 출력
			System.out.println(Arrays.toString(result));
			return;
		}
		for(int i=0;i<5;i++) {
			if(!visit[i]) { //시키지 않은 음식이라면
				result[def] = arr[i]; // 결과값에다 저장
				visit[i] = true;
				back(def+1); //다음 메뉴 선정하러 가기
				visit[i] = false;
			}
		}
	}

}

결과값

조합

조합이란 순열과비슷하게 n개 중 순서에 상관없에 r개의 원소를  뽑지만 순열과 다르게 *순서에 상관 없이 * 뽑는 경우의 수이다. 

공식 : nCr 

ex) 5종류의 음식 중에 2명이 먹을 음식을 시키는 경우(어짜피 갈라먹을꺼니까 니꺼 내꺼 신경쓰지말고 시키자!)

5*4/2*1 => 10

코드

package permu;

import java.util.Arrays;

public class zohap {
	static String arr[] = {"햄버거","피자","떡뽂이","샌드위치","김치찌개"};
	static boolean visit[];
	static String result[];
	static int N = 2; // 고르는 개수 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//5가지 메뉴중 2가지 골라야함 
		visit = new boolean[5];
		result = new String[2]; // 시킨 메뉴 저장 
		back(0,0);
	
	}
	private static void back(int def,int start) {
		// TODO Auto-generated method stub
		if(def==N) {//두가지 메뉴를 다 골랐다면 출력
			System.out.println(Arrays.toString(result));
			return;
		}
		for(int i=start;i<5;i++) {
			if(!visit[i]) { //시키지 않은 음식이라면
				result[def] = arr[i]; // 결과값에다 저장
				visit[i] = true;
				back(def+1,i+1); //다음 메뉴 선정하러 가기
				visit[i] = false;
			}
		}
	}

}

조합 코드에서 중요한 점은 start 변수도 넘겨준다는 것이다. 이 때 순열 코드 처음 짜는 사람들이 하는 국룰 실수  !!!!! 

back(def+1,start+1) --> 절대 안된다. i변수를 넣어야한다. 

결과값

부분집합 (power set)

집합의 원소로 이루어진 집합 (공집합도 포함 )

2^n (선택 하냐 안하냐로 2의 n임)

ex) 5종류의 음식가지고 0개부터 5개까지 시킬 수 있는 경우의 수

코드 

package permu;

import java.util.Arrays;

public class powerSet {
	static String arr[] = {"햄버거","피자","떡뽂이","샌드위치","김치찌개"};
	static boolean visit[];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		visit = new boolean[5];
		back(0);
	
	}
	private static void back(int def) {
		// TODO Auto-generated method stub
		if(def==5) {//다 돌았다면
			for(int i=0;i<5;i++) {
				if(visit[i]) {
					System.out.print(arr[i]+" ");
				}
			}
			System.out.println();
			return;
		}
		visit[def] = false;
		back(def+1);
		visit[def] = true;
		back(def+1);
	}

}

결과값

밑 부분 생략...

결과값에서 중요한 점은 마지막 공집합도 출력된다는 점이다. 만약 공집합이 필요없다면 이 부분 유의하며 코딩을 해야한다.