자바 알고리즘 / 조합, 순열, 부분 집합

조합

1번(추천)

import java.util.Arrays;
public class Combination1 {
	static int[] data; // 정수형 자료형의 모임.
	static int[] sel; // 내가 뽑은 것들을 저장할 배열
	static int N, R; // N개중 R개를 뽑자.

	public static void main(String[] args) {
		data = new int[] { 10, 11, 12, 13, 14 };
		N = 5;
		R = 3;
		sel = new int[R]; // R개의 값을 저장할 배열
		comb(0, 0);
	}// main

	// idx: 실제 data 배열의 인덱스, sidx: sel 배열의 인덱스
	static void comb(int idx, int sidx) {
    
		if (sidx == R) {
			System.out.println(Arrays.toString(sel));
			return;
		}
		if (idx == N) {
			// 다뽑지 못했는데 더이상 넣을지 말지 판단할 원소가 없다.
			return;
		}
		sel[sidx] = data[idx];
		comb(idx + 1, sidx + 1); // 뽑고 가고
		comb(idx + 1, sidx); // 안뽑고 가고

	}

}

2번

import java.util.Arrays;

public class Combination2 {
	static int[] data; // 정수형 자료형의 모임.
	static int[] sel; // 내가 뽑은 것들을 저장할 배열
	static int N, R; // N개중 R개를 뽑자.

	public static void main(String[] args) {
		data = new int[] { 10, 11, 12, 13, 14 };
		N = 5;
		R = 3;
		sel = new int[R]; // R개의 값을 저장할 배열
		comb(0, 0);
	}// main

	// idx: 실제 data 배열의 인덱스, sidx: sel 배열의 인덱스
	static void comb(int idx, int sidx) {
		if (sidx == R) {
			System.out.println(Arrays.toString(sel));
			return;
		}
		for(int i = idx ; i<=N-R+sidx; i++) {
			sel[sidx] = data[idx];
			comb(i+1, sidx + 1); // 뽑고 가고
		}
	}
}

순열

1번(추천)

import java.util.Arrays;

public class Permutation{

	static int[] nums;
	static boolean[] visited;
	static int[] result;
	static int N;

	public static void main(String[] args) {
		N = 3;
		nums = new int[] { 0, 1, 2 };
		result = new int[N];
		visited = new boolean[N];

		perm(0);

	}

	private static void perm(int idx) {
		if (idx == N) {
			System.out.println(Arrays.toString(result));
			return;
		}

		for (int i = 0; i < N; i++) {
			// 썼으면 쳐 내던지
			if (visited[i])
				continue;
			result[idx] = nums[i];
			visited[i] = true; //썼어
			perm(idx + 1);//내려가
			visited[i] = false;//안썼어
		}
	}

}

2번

import java.util.Arrays;

public class Permutation_swap {

	static int[] nums;
	static int N;

	public static void main(String[] args) {
		N = 3;
		nums = new int[] { 0, 1, 2 };
	
		perm(0);
		
	}
	
	//swap 메서드를 구현을 해보자.
	//인자로 배열과 바꿀 인덱스 2개를 넘길거냐 
	//인덱스 2개를 넘길거냐 
	static void swap(int a, int b) {
		int tmp = nums[a];
		nums[a] = nums[b];
		nums[b] = tmp;
	}
	//idx : 내가 판단하는 위치
	static void perm(int idx) {
		if(idx == N) {
			System.out.println(Arrays.toString(nums));
			return;
		}
		//자리를 바꾸면서 재귀 호출을 해본다.
		for(int i = idx; i<N; i++) {
			swap(i, idx);
			perm(idx+1);
			swap(i, idx);//원상복구
		}
	}
	
	
}

부분 집합

1번

public class Powerset1 {
	public static void main(String[] args) {
		
        //전체 경우의 수 판단.
		for(int i =0; i<(1<<N); i++) {
			//해당 i라는 부분집합에 판단.
			for(int j = 0; j<N; j++) {
				if(i &(1<<j) > 0){
					//너원소 있는거 
				}
			}
		}
	}
}

2번(추천)

public class Powerset2{
	public static void main(String[] args){
    int[] arr = {1,5,3,6,4};
    boolean[] visited = new boolean[5];
    int N = 5;
    
    recur(arr, visited, 0);
    }
    
    public void recur(int[] arr, boolean[] visited, int idx){
    
    if(idx == N){
    	for(int i = 0; i < N; i++){
    		if(visited[i]){
    			System.out.println(arr[i]);
    			}
    		}
    	return;
    }
    	visited[idx] = true;
        recur(arr, visited, idx + 1);
        visited[idx] = false;
        recur(arr, visited, idx + 1);
    
    
    }
}