Permutation & Combination

순열이란

서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 순열이라고 한다.

조합이란

조합은 집합에서 일부 원소를 취해 부분집합을 만드는 방법을 말한다.

코드

1. swap과정을 통한 순열만들기

import java.util.Arrays;

//순열 만들기
public class Permutation {
	static int[] arr = {1,2,3,4};
	
	public static void main(String[] args) {
		perm(0);
	}
	
	static void perm(int k) {
		if(k== arr.length) {
			System.out.println(Arrays.toString(arr));
			return ;
		}
		for (int i = k; i < arr.length; i++) {
			swap(i,k);
			perm(k+1);
			swap(i,k);							//백트래킹
		}
	}
	
	static void swap(int i ,int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}

2. used[] 배열을 이용하여 (사용한 카드는 체킹) 이용하여 순열만들기

import java.util.LinkedList;
import java.util.List;

//순열 만들기2
public class Permutation2 {
	static String[] arr = {"1","2","3","4"};
	static boolean[] used = new boolean[arr.length];

	static List<String>	result = new LinkedList<>();
	
	static int total = 0;
	public static void main(String[] args) {
		perm(0,4);
		System.out.println(total);
	}
	static void perm(int cnt , int r) {			//cnt 현재 뽑은 갯수,r 총 뽑아야하는 카드 수
		if(cnt == r) {
			total++;
			System.out.println(result);
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			if(!used[i]) {						//i번이 (사용가능상태라면)
				result.add(arr[i]);				//result에 추가한다.			//i번 카드를 내가 사용할게
				used[i] = true;
				perm(cnt+1,r);					//다음재귀한테 다음거 뽑아봐~햇다.
				used[i] = false;
				result.remove(arr[i]);
			}
		}
	}
}