순열과 조합

1. 순열

 

- 중복을 허용하지 않고, depth를 이용하는 방법

static void permutation(int[] arr, int depth, int n, int k) {
	if (depth == k) {
    	for (int i = 0; i < arr.length; i++) {
        	if (i == k-1) System.out.println(arr[i]);
            else System.out.print(arr[i] + " ");
        }
        retrun;
    }
    
    for (int i = depth; i < n; i++) {
    	swap(arr, i, depth);	//현재 위치의 값과 i위치의 값을 바꿈
        permutation(arr, depth + 1, n, k);
        swap(arr, i, depth);	//해당 위치 탐색 끝났으면 원상 복구
    }
}

static void swap(int[] arr, int i, int j) {
	int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

 

- 중복을 허용하지 않고, boolean[] isVisited 배열과 LinkedList를 사용하는 방법

static void permutation(int n, int k) {
	if (list.size() == k) {
    	for(int num: list) {
        	System.out.print(num + " ");
        }
        System.out.println();
        return;
    }
    
    for(int i = 1; i <= n; i++) {
    	if(!isVisited[i]) {
            list.add(i);
            isVisited[i] = true;
            permutation(n, k);
            isVisited[i] = false;
            list.removeLast();
        }
    }
}

 

- 중복을 허용하고, boolean[] isVisited 배열과 LinkedList를 사용하는 방법

for(int i = 1; i <= n; i++) {
    list.add(i);
    permutation(n, k);
    list.removeLast();
}

 

 

2. 조합

 

- 중복을 허용하지 않고, comArr 배열을 사용하는 방법

static void combination(int n, int r, int idx, int target) {
	if (r == 0) {
    	for(int num: comArr) System.out.print(num + " ");
    	System.out.println();
        return;
    }
    
    if (target == n+1) return;
    
    comArr[idx] = target;
    combination(n, r - 1, idx + 1, target + 1);	//idx 자리에 숫자를 삽입하고, 다음 숫자 후보로 넘어감
    combination(n, r, idx, target + 1);	//해당 위치	//idx 자리에 다음 숫자 후보를 삽입하기 위해 숫자를 삽입하지 않고 넘어감
    
}

 

- 중복을 허용하고, comArr 배열을 사용하는 방법

comArr[i] = target;
combination(n, r - 1, idx + 1, target);
combination(n, r, idx, target + 1);