자바에서 순열과 조합

요즘은 자바로 코테를 준비하고 있는데,자바는 놀랍게도 순열, 조합 라이브러리가 없어서 파이썬이면 1줄만에 끝나는 뽑기를 직접 한땀한땀 구현해야 한다. 너무나도 충격적;;

아무튼 몇 번 자바로 이런 문제를 풀다보니 손에 익은 풀이가 생겨서 정리하려고 한다. 인터넷 허용 안되는 시험이라면 그때그때 상황에 맞게 효율적으로 짜겠지만...인터넷 허용이라면 이 포스팅의 순열,조합 함수를 긁어 쓸 생각이다.^_^

뭘 뽑을지는 문제마다 다르므로 차라리 사용할 인덱스만 뽑아서 output 배열에 넣는게 다양한 문제에 적용하기 좋을 것 같다.(0,1,2...~n중 r개를 뽑기)

순열

 
import java.util.*;
import java.io.*;

public class Main {
	public static int [] index;
	public static int [] output;
	public static int n,r;
	public static boolean [] visited;
	public static void main(String[] args) throws Exception {
		//n개 중 r개를 뽑는다. 문제에 따라 바꿔 주기.
		 n=3;
		 r=2;
		 output=new int[r];
		 visited=new boolean[n];
		 
		 perm(0);
	}
	//순열
	public static void perm(int cnt) {
		if(cnt==r) {
			//뽑힌 인덱스의 목록
			System.out.println(Arrays.toString(output));
			return;
		}
		for(int i=0;i<n;i++) {
			if(visited[i]) continue; 
			output[cnt]=i;
			visited[i]=true;
			perm(cnt+1);
			visited[i]=false;
		}
	}
 
}

조합

import java.util.*;
import java.io.*;

public class Main {
	public static int [] index;
	public static int [] output;
	public static int n,r;
	public static void main(String[] args) throws Exception {
		//n개 중 r개를 뽑는다. 문제에 따라 바꿔 주기.
		 n=3;
		 r=2;
		 output=new int[r];
		 combi(0,0);
	}
	//조합
	public static void combi(int cnt,int start) {
		if(cnt==r) {
			//뽑힌 인덱스의 목록
			System.out.println(Arrays.toString(output));
			return;
		}
		for(int i=start;i<n;i++) {		 
			output[cnt]=i;
			combi(cnt+1,i+1);
			 
		}
	}
 
}