Java 순열과 조합

<Permutation>

package practice;

import java.util.Arrays;
import java.util.Scanner;

public class PermutationTest1 {
	
	static int n;
	static int r;

	static char[] numbers;
	static boolean[] visited;
	static int res;
	static char[] data = {'a','b','c','d','e'};
	
	//nPn
	//nPr
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		r = sc.nextInt();
		
		res = 0;
		
		numbers= new char[r];
		
		
		visited = new boolean[n+1];
		permu(0);
		System.out.println(res);
	}
	
	public static void permu(int cnt) {
		if (cnt == r) {
			res++;
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for (int i = 0; i < n; i++) {
			if(visited[i]) 
				continue;
			numbers[cnt] = data[i]; //visited관련 메소드를 없애버리면 중복순열
			visited[i] = true;
			permu(cnt+1);
			visited[i] = false;	
		}
		
		
	}

}

- NextPermutation

현 순열에서 사전 순으로 다음 순열 생성

 

1. 배열을 오름차순으로 정렬한 후 시작(가장 작은 순열부터 시작)

2. 꼭대기의 바로 앞자리(i-1)의 값을 크게 만들 교환 값 뒤쪽에서 찾기 

3. i-1값과 j 교환

4. i부터 끝까지 오름차순으로 변경

private static boolean np(int numbers[]) {
    totalCount++;
    int N = numbers.length;

    //뒤 -> 앞
    // 1. 꼭대기에서 떨어지는 숫자를 찾는다(꼭대기 찾기)
    /*ex)127543가 있다면 3,4,5,7은 증가하는 부분을 가지고 있지만 7,2부분에서 갑자기 뚝 떨어진다
        즉 7은 꼭대기가 되며 2는 꼭대기에서 꺾인 부분을 의미한다
     */
    int i=N-1;
    while(i>0 && numbers[i-1]>=numbers[i])  i--;

    if(i==0) 
        return false;

    // 2. 꼭대기의 바로 앞자리(i-1)의 값을 크게 만들 교환 값 뒤쪽에서 찾기 
    //127543에서 2(꺾여서 떨어진 부분)를 찾았다면 7543를 뒤부터 탐색해서 2보다 큰값이랑 swap해준다
    int j=N-1;
    while(numbers[i-1]>=numbers[j])	j--;

    //3. i-1값과 j 교환
    swap(numbers,i-1,j);

    // 4. i부터 끝까지 오름차순으로 변경
    //swap하면 7542가 될텐데 이 부분을 오름차순 해준다
    Arrays.sort(numbers, i, N); 		
//		int k = N-1;
//		while(i<k) {
//			swap(numbers,i++,k--);			
//		}
    return true;
}

<Combination>

package practice;

import java.util.Arrays;
import java.util.Scanner;

public class CombinationTest {
	
	static int n,r,res;
	static int[] numbers,input;

	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		r = sc.nextInt();
		
		input = new int[n];
		numbers = new int[r];
		
		for (int i = 0; i < n; i++) {
			input[i] = sc.nextInt();
		}

		combi(0,0);
		
	}
	
	public static void combi(int cnt,int start) {
		if (cnt == r) {
			res++;
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for (int i = start; i < n; i++) {
			numbers[cnt] = input[i];
			combi(cnt+1,i+1); //combi(cnt+1,i)로 하면 중복조합
		}
		
		
	}

}

- 단순히 nCk를 구할 때 쓰는 법

	// n개 중 k개를 뽑는 조합의 경우의 수 리턴 
	public static int combination(int n, int k){
		if(n==k || k == 0){
			return 1;
		}
		// n-1번째까지 k개를 다 뽑는 경우의 수(n번째원소 조합에 포함시키지 않음)와 
		// n-1번째까지 k-1개를 다 뽑는 경우의수(n번째원소 조합에 포함시킴)를 더한다.
		return combination(n-1, k) +  combination(n-1, k-1);	
	}
	
	public static void main(String[] args) {

		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int k = s.nextInt();
		
		System.out.println(combination(n, k));
		
	}