부분집합/순열/조합

부분 집합

하나하나 다 아무것도 안 고를 때부터 다 골랐을 때까지 골라줄 때

ex) 1,2,3,4,5

(),1,2,3,4,5,(1,2),(1,3),...,(1,2,3),.....,(1,2,3,4,5)

package 구현;

public class 부분집합 {
	static int N;
	static String ans;
	static String[] 재료;
	static boolean[] sel;
	
	public static void main(String[] args) {
		재료=new String[] {"삼","단","우"};
		N=재료.length;
//		System.out.println(N);
		sel=new boolean[N];
		powerset(0);
		
	}

	private static void powerset(int n) {
		if (n==N) {
			ans="";
			for (int i = 0; i < N; i++) {
				if (sel[i]) {
					ans+=재료[i];
				}
			}
			System.out.println(ans);
			return;
		}
		sel[n]=true;
		powerset(n+1);
		sel[n]=false;
		powerset(n+1);
	}
}
//
삼단우
삼단
삼우
삼
단우
단
우

마지막 공백도 출력의 일부분 아무것도 고르지 않았을 때의 출력

순열

숫자의 모든 경우의 수를 구해줄 때

ex) 1~4까지의 수 중 2개의 경우의 수

1,2/1,3/1,4/2,1/2,3/..../4,2/4,3

package 구현;

import java.util.Scanner;

public class 순열 {
	static int N,M,arr[];
	static boolean[] visit;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		arr=new int[M];
		visit=new boolean[N];
		soonten(0);
	}

	private static void soonten(int n) {
		if (n==M) {
			for (int i = 0; i < M; i++) {
				System.out.print(arr[i]+" ");
			}
			System.out.println();
			return;
		}
		for (int i = 0; i < N; i++) {
			if (visit[i]) {
				continue;
			}
			arr[n]=i+1;
			visit[i]=true;
			soonten(n+1);
			visit[i]=false;
		}
	}
}

중복순열

모든 숫자의 경우의 수를 구해줄 때 중복까지 허용

ex)1~4까지의 수 중 2개의 경우의 수

1,1/1,2/1,3/1,4/2,1/2,2/...../4,3/4,4

package 구현;

import java.util.Scanner;

public class 중복순열 {
	static int N,M,arr[];
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		arr=new int[M];
		soonten(0);
	}

	private static void soonten(int n) {
		if (n==M) {
			for (int i = 0; i < M; i++) {
				System.out.print(arr[i]+" ");
			}
			System.out.println();
			return;
		}
		for (int i = 1; i <= N; i++) {
			arr[n]=i;
			soonten(n+1);
		}
	}
}

조합

모든 수의 경우의 수 중 같은 경우는 뺀 것

ex) 1~4의 숫자 중 2개의 숫자를 고르는 경우

1,2/1,3/1,4/2,3/2,4/3,4

package 구현;

import java.util.Scanner;

public class 조합 {
	static int N,M,arr[];
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		arr=new int[M];
		comb(0,1);
	}

	private static void comb(int n, int start) {
		if (n==M) {
			for (int i = 0; i < M; i++) {
				System.out.print(arr[i]+" ");
			}
			System.out.println();
			return;
		}
		for (int i = start; i <= N; i++) {
			arr[n]=i;
			comb(n+1,i+1);
		}
	}
}

중복 조합

모든 수의 경우 중 겹치는 것은 빼지만 중복은 허용하여 고를 경우

ex) 1~4중 2개의 경우를 조합

1,1/1,2/1,3/1,4/2,2/2,3/2,4/3,3/3,4

package 구현;

import java.util.Scanner;

public class 중복조합 {
	static int N,M,arr[];
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		arr=new int[M];
		comb(0,1);
	}

	private static void comb(int n, int start) {
		if (n==M) {
			for (int i = 0; i < M; i++) {
				System.out.print(arr[i]+" ");
			}
			System.out.println();
			return;
		}
		for (int i = start; i <= N; i++) {
			arr[n]=i;
			comb(n+1,i);
		}
	}
}

부분 집합	순열	중복 순열	조합	중복 조합
sel[]의 boolean 배열을 사용하여 true,false를 사용하여 true일 때 답을 골라줄 수 있다.	visit[] boolean 배열을 사용하여 들렸던 곳을  true처리 해줘 그곳을 건너뛰어 중복을 피해줄 수 있다.		조합 메소드에 일단 인덱스와 시작 값 두개를 넣어줘야된다. 그리고 재귀를 넘겨줄 때, i+1을 주어 중복을 피해줄 수 있다.	일단 조합과 다르게 재귀를 넘겨줄 때 그냥 i만 넘겨주면 중복을 해서 조합을 해줄 수 있다.