[JAVA] 순열과 조합

순열 구하기 ideation

순열은 순서를 고려하여 중복되지 않는 값들을 조합하는 것이다.

이번 차례에서 'a'를 선택하고 (방문처리를 하고), 그 다음 선택지에서 대상이 되는 배열에서 'a'를 제외하고 순회하여 선택한다.

몇번째 선택이냐를 나타내는 depth를 주목하자.

순열 구현하기

	static void perm(int depth, int r) {
		
		if(depth==R) {
			for(int i=0; i<R; i++) {
				System.out.print(output[i]+" ");
			}
			System.out.println();
			return;
		}
		
		for(int i=0; i<N; i++) {
			//선택을 하는 경우와 하지 않는 경우
			if(!visited[i]) {
				output[depth] = arr[i];
				visited[i]=true;
                //분기가 나누어지는 구간으로, 이번 차례에서 방문처리를 해주었다면
                //다음 노드에서
				perm(depth+1,r-1);
				visited[i] = false;
			}
			
		}
		
	}

전체 사용하기

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


public class Main {
	
	static int N,R;
	static int []  arr;
	static int []  output;
	static boolean[] visited;
	
	static void perm(int depth, int r) {
		
		if(depth==R) {
			for(int i=0; i<R; i++) {
				System.out.print(output[i]+" ");
			}
			System.out.println();
			return;
		}
		
		for(int i=0; i<N; i++) {
			//선택을 하는 경우와 하지 않는 경우
			if(!visited[i]) {
				output[depth] = arr[i];
				visited[i]=true;
				perm(depth+1,r-1);
				visited[i] = false;
			}	
		}
	}
	
	public static void main(String [] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		arr = new int[N];	
		output = new int[R];
		visited = new boolean[N];
		for(int i=1; i<=N; i++) {
			arr[i-1] = i;
		}
		perm(0,R);
		
	}
	

}

입력

4 2

출력

4 2
1 2 
1 3 
1 4 
2 1 
2 3 
2 4 
3 1 
3 2 
3 4 
4 1 
4 2 
4 3 

조합 구하기 ideation

조합은 순서가 상관이 없다. => 따라서 방문처리 된 아이들만 출력해주면 된다.

	static void combination(int start, int r) {
		
	    if(r == 0) {
	        for(int i=0; i<N; i++) {
	        	if(visited[i])System.out.print(arr[i]+" ");
	        }
	        System.out.println();
	        return;
	    } 

	    for(int i=start; i<N; i++) {
	    	//선택처리
	        visited[i] = true;
            //요기 조심 combi(start+1, r-1) 이 아니니까..
	        combination(i + 1, r - 1);
	        visited[i] = false;
	    }
	}

전체코드

package Perm;


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


public class combi {
	
	static int N,R;
	static int []  arr;
	static int []  output;
	static boolean[] visited;
	
	
	//
	static void combination(int start, int r) {
		
	    if(r == 0) {
	        for(int i=0; i<N; i++) {
	        	if(visited[i])System.out.print(arr[i]+" ");
	        }
	        System.out.println();
	        return;
	    } 

	    for(int i=start; i<N; i++) {
	    	//선택처리
	        visited[i] = true;
	        combination( i + 1, r - 1);
	        visited[i] = false;
	    }
	}
		
	
	
	public static void main(String [] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		arr = new int[N];	
		output = new int[R];
		visited = new boolean[N];
		for(int i=1; i<=N; i++) {
			arr[i-1] = i;
		}
		combination(0,2);
		
	}
	

}

입력
4 2
출력
1 2
1 3
1 4
2 3
2 4
3 4