순열과 조합 뿌시기

1. 순열

1) 순열이란? {1,2,3}이 주어졌을 때, {1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}처럼 순서를 바꿔서 나타낼수 있는

모든 경우를 말한다

 

2) 코드

크기가 3인 배열의 순열을 구했다.

public class 순열 {
	static String fruits[] = {"사과", "바나나", "딸기"};
	static boolean check[]= new boolean[3];
	static String[] sel = new String[3];
	public static void main(String[] args) {
		perm(0);
	}
	static void perm(int select_idx) {
		if(select_idx == fruits.length) {
			System.out.println(Arrays.toString(sel));
			return;
		}
		for (int i = 0; i < fruits.length; i++) {
			if(check[i]) continue;
			check[i] = true;
			sel[select_idx] = fruits[i];
			perm(select_idx+1);
			check[i] = false;
		}
	}
}

출력값

위의 코드 실행 일부...

 

- 파이썬 코드 (swap 사용)

def perm(arr, depth, N):
    if N == depth:
        print(arr)
        return

    for i in range(depth, N):
        swap(arr, depth, i)
        perm(arr, depth+1, N)
        swap(arr, depth, i)

def swap(arr, depth, i):
    temp = arr[depth]
    arr[depth] = arr[i]
    arr[i] = temp



N = int(input())
lists = list(map(int, input().split()))
arr = [i+1 for i in range(N)]
if lists[0] ==1 :
    perm(arr, 0, N)

 

2. 조합

1) 조합이란? 배열에서 순서에 상관없이 n개를 선택해서 만들수 있는 부분집합

 

2) 조합 코드

반복문을 사용해서 크기가 3인 배열에서 2개를 선택하는 경우

시작 index하고 선택index가 필요하다.

import java.util.Arrays;

public class 반복문_조합 {
	//2를 고르기
	static String fruits[] = {"사과", "바나나", "딸기"};
	static String sel[] = new String[3];
	public static void main(String[] args) {
		comb2(0,0);
	}
	static void comb2(int start_idx, int select_idx) {
		if(select_idx == 2) {
			System.out.println(Arrays.toString(sel));
			return;
		}
		for (int i = start_idx; i < fruits.length; i++) {
			sel[select_idx] = fruits[i];
			comb2(i+1, select_idx+1);
			sel[select_idx] = "";
		}
	}
}

 

재귀만을 이용하여 배열에서 2개를 선택 코드.

순열과 다른점은 for문으로 전체배열을 탐색해주는 코드 없기 때문에 따로

전체 배열을 탐색할 수 있게 파라미터를 같이 호출해 줘야 한다.

import java.util.Arrays;

public class 조합 {
	//모든 조합을 구해라
	static String fruits[] = {"사과", "바나나", "딸기"};
	static String sel[] = new String[3];
	public static void main(String[] args) {
		comb(0,0);
	}
	static void comb(int arr_idx, int select_idx) {
		if(select_idx == 2) {
			System.out.println(Arrays.toString(sel));
			return;
		}
		if(arr_idx == fruits.length) {
			return;
		}
		sel[select_idx] = fruits[arr_idx];
		comb(arr_idx+1, select_idx+1);
		sel[select_idx] = "";
		comb(arr_idx+1, select_idx);
	}
}

 

3. 부분집합

import java.util.Arrays;

public class 조합 {
	//모든 조합을 구해라
	static String fruits[] = {"사과", "바나나", "딸기"};
	static String sel[] = new String[3];
	public static void main(String[] args) {
		comb(0,0);
	}
	static void comb(int arr_idx, int select_idx) {
		if(arr_idx == 3) {
			for (String s : sel) {
				System.out.print(s+" ");
			}
			System.out.println();
			return;
		}
		sel[select_idx] = fruits[arr_idx];
		comb(arr_idx+1, select_idx+1);
		sel[select_idx] = "";
		comb(arr_idx+1, select_idx);
	}
}

출력값