순열
"순서 있게 나열하는 것"
-> "누가 먼저 나오느냐"가 다르면 다른 경우로 셈한다.
예시)
{1, 2, 3} 중 2개를 선택하는 것은 (1,2) (1,3) (2,1) (2,3) (3,1) (3,2) 총 6개다.
관련 코드
첫째 줄에 전체 원소 개수 N, 뽑을 원소 개수 R
둘째 줄에 배열 정보가 주어질 때, 가능한 순열, 중복 순열 경우를 모두 출력하는 코드이다.
*핵심은 perm 함수의 매개변수가 depth(길이)를 뜻한다는 것을 알아야 한다.
자바
class Solution
{
static int N;
static int R;
static int[] arr;
static ArrayList<int[]> result;
static boolean[] visited;
static int[] temp_result;
public static void main(String args[]) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 전체 원소 개수
R = Integer.parseInt(st.nextToken()); // 뽑을 원소 개수
arr = new int[N]; // 주어진 원소 배열
result = new ArrayList<>(); // 순열 결과 저장할 리스트
visited = new boolean[N]; // 방문 상태 저장 배열
temp_result = new int[R]; // 현재까지 구성된 배열(완성되면 결과에 저장)
// 원소들 입력 받고 사전식 정렬
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
Arrays.sort(arr);
// 순열 수행
perm(0);
for(int i = 0; i < result.size(); i ++) {
for(int j = 0; j < R; j++) {
System.out.print(result.get(i)[j] + " ");
}
System.out.println();
}
}
static void perm(int depth) {
if(depth == R) {
result.add(temp_result.clone());
return;
}
for(int i = 0; i < N; i++) {
if(!visited[i]) {
visited[i] = true;
temp_result[depth] = arr[i];
perm(depth+1);
visited[i] = false;
}
}
}
}
// 입력
3 2
1 2 3
// 출력
1 2
1 3
2 1
2 3
3 1
3 2 중복 순열
같은 원소를 여러 번 뽑을 수 있고, 순서가 다르면 다른 경우이다.
예시)
{1, 2, 3} 중 2개를 선택하는 것은 (1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3) 총 9개다.
위 코드에서 visited 배열의 사용만 제외시키면 된다. 그러면 방문한 원소도 재방문하기 때문이다.
일반 순열
static void perm(int depth) {
if(depth == R) {
result.add(temp_result.clone());
return;
}
for(int i = 0; i < N; i++) {
if(!visited[i]) {
visited[i] = true;
temp_result[depth] = arr[i];
perm(depth+1);
visited[i] = false;
}
}
}
// 입력
3 2
1 2 3
// 출력
1 2
1 3
2 1
2 3
3 1
3 2 중복 순열
static void perm(int depth) {
if(depth == R) {
result.add(temp_result.clone());
return;
}
for(int i = 0; i < N; i++) {
temp_result[depth] = arr[i];
perm(depth+1);
}
}
// 입력
3 2
1 2 3
// 출력
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3 조합
순서 상관 없이 뽑는 것
예시)
{1, 2, 3} 중 2개를 선택하는 것은 (1,2) (1,3) (2,3) 총 3개다.
start 매개변수를 사용해 자신의 이후부터의 값을 선택하도록 하면 된다. visited 방문 배열은 필요 없다.
class Solution
{
static int N;
static int R;
static int[] arr;
static ArrayList<int[]> result;
static int[] temp_result;
public static void main(String args[]) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 전체 원소 개수
R = Integer.parseInt(st.nextToken()); // 뽑을 원소 개수
arr = new int[N]; // 주어진 원소 배열
result = new ArrayList<>(); // 순열 결과 저장할 리스트
temp_result = new int[R]; // 현재까지 구성된 배열(완성되면 결과에 저장)
// 원소들 입력 받고 사전식 정렬
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
Arrays.sort(arr);
// 순열 수행
comb(0, 0);
for(int i = 0; i < result.size(); i ++) {
for(int j = 0; j < R; j++) {
System.out.print(result.get(i)[j] + " ");
}
System.out.println();
}
}
static void comb(int start, int depth) {
if(depth == R) {
result.add(temp_result.clone());
return;
}
for(int i = start; i < N; i++) {
temp_result[depth] = arr[i];
comb(start+1, depth+1);
}
}
}
// 입력
3 2
// 출력
1 2
1 3
2 3 중복 조합
같은 원소를 여러 번 뽑을 수 있지만, 순서 상관없이 묶음만 본다.
예시)
{1, 2, 3} 중 2개를 선택하는 것은 (1,1) (1,2) (1,3) (2,2) (2,3) (3,3) 총 6개다.
위 코드에서 comb(i+1, depth+1) 을 comb(i, depth+1) 로 수정해주면 된다. 중복 조합인 경우 자신을 중복해서 선택할 수 있기 때문이다.
일반 조합
static void comb(int start, int depth) {
if(depth == R) {
result.add(temp_result.clone());
return;
}
for(int i = start; i < N; i++) {
temp_result[depth] = arr[i];
comb(i+1, depth+1);
}
}
// 입력
3 2
// 출력
1 2
1 3
2 3 중복 조합
static void comb(int start, int depth) {
if(depth == R) {
result.add(temp_result.clone());
return;
}
for(int i = start; i < N; i++) {
temp_result[depth] = arr[i];
comb(i, depth+1);
}
}
// 입력
3 2
1 2 3
// 출력
1 1
1 2
1 3
2 2
2 3
3 3 
better than yesterday