[Java] 순열 - 조합 - 부분집합 정리

Java 순열 구현

 

1. Permutation 1 (idx 활용)

public class Permutation1 {
	
	static int N;				// 원소의 개수 
	static int R;				// 뽑을 개수 
	static int[] data;			// 입력받은 data
	static int[] numbers;			// 순열을 담을 배열 
			
	public static void main(String[] args) {
		
		data = new int[] {1, 2, 3};
		N = data.length;
		R = data.length;
		numbers = new int[R];
		
		permutation(0);
	}
	
	public static void permutation(int idx) {
		if(idx == R) {
			System.out.println(Arrays.toString(numbers));
		}
		
		top:
		for(int i = 0; i < N; i++) {
			// 중복 검사
			for(int j = 0; j < idx; j++) {
				if(numbers[j] == data[i]) {
					// 중복된 경우
					continue top;
				}
			}
			numbers[idx] = data[i];
			permutation(idx + 1);
		}
	}

}

 

[출력 결과]

 

 

2. Permutation 1 (flag 활용)

public class Permutation2 {

	
	static int N;					// 원소의 개수 
	static int R;					// 뽑을 개수 
	static int[] data;				// 입력받은 data
	static int[] numbers;				// 순열을 담을 배열 
	static boolean[] isSelected;			// 중복을 체크하기 위한 배열 
			
	public static void main(String[] args) {

		
		data = new int[] {1, 2, 3};
		
		N = data.length;
		R = data.length;
		numbers = new int[R];
		isSelected = new boolean[N];
		
		permutation(0);
	}
	
	public static void permutation(int idx) {
		if(idx == R) {
			System.out.println(Arrays.toString(numbers));
		}
		
		for(int i = 0; i < N; i++) {
			// 중복 검사
			if(isSelected[i]) continue;
			numbers[idx] = data[i];
			isSelected[i] = true;
			permutation(idx+1);
			isSelected[i] = false;
		}
	}

}

[출력 결과]

 

 

3. bitmask 활용

public class Permutation3 {

	
	static int N;					// 원소의 개수 
	static int R;					// 뽑을 개수 
	static int[] data;				// 입력받은 data
	static int[] numbers;				// 순열을 담을 배열 

	
	/**
	 * 
	 * @param idx 	뽑을 원소의 위치
	 * @param flag  원소 중복 체크를 위한 flag
	 */
	public static void main(String[] args) {

		
		data = new int[] {1, 2, 3};
		
		N = data.length;
		R = data.length;
		numbers = new int[R];
		
		permutation(0, 0);
	}
	
	public static void permutation(int idx, int flag) {
		if(idx == R) {
			System.out.println(Arrays.toString(numbers));
			return ;
		}
		
		for(int i = 0; i < N; i++) {
			// 중복 검사
			if((flag & 1 << i) != 0) continue;
			numbers[idx] = data[i];
			permutation(idx + 1, flag | 1 << i);
		}
	}

}

 

[실행 결과]

 

 

4. swap 

 

static int[] data = {1, 2, 3, 4, 5};
    static int cnt = 0;

    
	public static void main(String[] args) {
		
		perm(0);
		System.out.println(cnt);
	}
    
	public static void perm(int depth) {
		
		// 뽑고 싶은 수만큼 뽑음
		if(depth == 3) {
			cnt++;
			System.out.println(Arrays.toString(data));
			return;
		}
		
		for(int i = depth; i < data.length; i++) {
			swap(i, depth);
			perm(depth + 1);
			swap(depth, i);
		}
		
	}
    
    
    public static void swap(int i, int j) {
    	int temp = data[i];
    	data[i] = data[j];
    	data[j] = temp;
    }

 

5P3 - 앞의 3자리만 보길

 

Java 조합 구현

 

<1> 

	static int[] selected = new int[2];
    static int cnt = 0;

    
	public static void main(String[] args) {

		combi(1, 0);
		System.out.println(cnt);
	}
    
    
    
    public static void combi(int start, int depth){
        if(depth == 2){
        	cnt++;
            System.out.println(Arrays.toString(selected));
            return;
        }
        
        for(int i = start; i <= 4; i++){
        	selected[depth] = i;
            combi(i + 1, depth + 1);
        }
    }

 

 

 

Java 부분 집합 구현

static int[] data = {1, 2, 3, 4};
    static boolean[] selected = new boolean[4];
    static int cnt = 0;

    
	public static void main(String[] args) {
		
		subset(0);
		System.out.println(cnt);
	}
    
	public static void subset(int depth) {
		
		// 뽑고 싶은 수만큼 뽑음
		if(depth == 4) {
			cnt++;
			for(int i = 0; i < 4; i++) {
				if(selected[i]) {
					System.out.print(data[i] + " ");
				}
			}
			System.out.println();
			return;
		}

		selected[depth] = true;
		subset(depth + 1);
		selected[depth] = false;
		subset(depth + 1);
		
	}