[Java] 순열(Permutation)

본 글에서는 java에서 순열을 작성하는 방법을 알아봅니다.

순열

• 중복 없는 n개의 수열에서 순서를 고려하여 중복없이 r개를 선택하는 것을 의미합니다.
• 위 문장을 수학적 기호로 나타내면 $nPr$ 입니다.
  
  

실생활과 순열

• 순열은 생활 속에서도 자주 접할 수 있는 개념입니다.

1. 책장을 정리중이다. 책을 어떤 순서로 꽂을까?
2. 놀러가는 3일동안 각 날짜별로 어떤 옷을 입을까?

• 코딩은 결국 실생활에 존재하는 문제를 컴퓨터의 언어로 바꾸어 전달하는 것입니다. 실생활에서 자주 접할 수 있는 순열을 컴퓨터에게 어떻게 명령할지 나만의 코드 스니펫으로 잘 기억하고 있는 것은 코딩을 효율적으로 만들어줄 수 있습니다.
  
  

반복문과 재귀

• 프로그래밍에서 모든 반복문은 재귀문으로, 모든 재귀문은 반복문으로 변환이 가능합니다.
• 그렇기 때문에 반복 처리가 필요한 경우 한가지 방법으로만 구현할 수 있으나 상황에 맞게 유리한 방법을 선택해 구현하는 것이 효율적입니다.
• 반복문을 사용할지 재귀를 사용할지 판단하는 기준은 보통 다음과 같습니다.

반복문 사용 → 반복문이 몇 번 중첩되는지 알며, 그 중첩의 깊이가 깊지 않을 때
재귀 사용 → 반복문의 중첩 깊이가 동적일 때

• 순열은 일반적으로 재귀를 사용해 구현합니다. n개의 원소중 몇 개의 원소를 선택해 순열을 구성할지 정해지지 않은 문제상황이 있기 때문입니다. 또한 안다고 하더라도 5개의 원소를 선택해 순열을 구성한다면? 5중 반복문을 구현해야합니다.

		// 원소를 뽑을 수열
        int[] nums = {1, 2, 3, 4, 5, 6, 7};

        // 동일한 원소를 뽑지 않기 위해 중복 체크
        boolean[] check = new boolean[nums.length];

        // nums에서 5개를 뽑아 순열을 구성할 배열
        int[] permutation = new int[5];

        for(int i = 0; i < nums.length; ++i) {
            check[i] = true;
            permutation[0] = nums[i];

            for(int j = 0; j < nums.length; ++j) {
                if (check[j]) continue;
                check[j] = true;
                permutation[1] = nums[j];

                for(int k = 0; k < nums.length; ++k) {
                    if (check[k]) continue;
                    check[k] = true;
                    permutation[2] = nums[k];

                    for(int l = 0; l < nums.length; ++l) {
                        if (check[l]) continue;
                        check[l] = true;
                        permutation[3] = nums[l];

                        for(int m = 0; m < nums.length; ++m) {
                            if (check[m]) continue;
                            permutation[4] = nums[m];
                            System.out.println(Arrays.toString(permutation));
                        }
                        check[l] = false;
                    }
                    check[k] = false;
                }
                check[j] = false;
            }
            check[i] = false;
        }

• 보기만 해도 어질어질합니다. 가독성이 떨어짐은 물론이고 반복되는 코드는 개발자에게 알러지를 일으키기에 충분해보입니다.
• 순열 코드는 아래와 같이 재귀를 이용해 작성합니다.
  
  

java에서의 전형적인 순열 코드

• 외우려고 노력하기보다, 이미 잘 작성된 코드를 한 번 이해한 후 본인의 스타일대로 직접 구현해보면 금방 체득됩니다.

import java.io.*;
import java.util.*;

class Main {
	static List<Integer> input = new ArrayList<>(); // 입력받은 수의 집합
	static int n, r;
	
	static int count; 
	static int[] data; // 순열을 구성할 데이터
	static boolean[] check;
	
	// index번째 원소를 뽑아 순열을 구성한다.
	static void permutation(int index) {
		
		// index가 r에 다다르면 원하는 행위를 한다. 
		if (index == r) {
			
			// 순열 출력 
			count++;
			System.out.println("#" + count + " " + Arrays.toString(data));
			
			return;
		}
		
		// i 번째 원소를 뽑는다.
		for (int i = 0; i < n; ++i) {
			
			// 이미 뽑힌 원소는 뽑지 않는다.
			if (check[i]) continue;
			
			check[i] = true;
			data[index] = input.get(i);
			permutation(index + 1);
			
			// 다음 원소 뽑을 준비
			check[i] = false;
		}
	}
	
	public static void main(String[] args) throws Exception {
		System.out.println("nPr 출력 프로그램");
		
		// 수열 입력
		System.out.print("수열 입력: ");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		while (st.hasMoreTokens()) {
			input.add(Integer.parseInt(st.nextToken()));
		}
		
		// r 입력 및 변수 초기화
		System.out.print("r 입력: ");
		r = Integer.parseInt(br.readLine());
		
		n = input.size();
		check = new boolean[n];
		data = new int[r];
		
		permutation(0);
	}
}

• 순열의 기본적인 형태를 잘 작성할 수 있게 되었다면, 몇가지 변형을 해보며 다양한 상황에 응용 가능하도록 연습해보면 좋겠죠?

• 위 코드에서 boolean[] check를 통해 중복체크했던 부분을 java에서 성능 최적화를 위해 자주 사용되는 기법인 비트마스킹으로 변형해보겠습니다.
  (참고: 순열 코드에서 중복체크를 비트마스킹으로 하는 것 만으로 큰 성능차이는 발생하지 않습니다. 오히려 가독성 저하 및 디버깅 난이도 상승을 불러올 수 있으므로 상황에 맞게 사용해야합니다.)
  
  

bitmasking 기법으로 중복 체크

import java.io.*;
import java.util.*;

class Main {
	static List<Integer> input = new ArrayList<>(); // 입력받은 수의 집합
	static int n, r;
	
	static int count; 
	static int[] data; // 순열을 구성할 데이터
	
	// index번째 원소를 뽑아 순열을 구성한다.
	static void permutation(int index, int mask) {
		
		// index가 r에 다다르면 원하는 행위를 한다. 
		if (index == r) {
			
			// 순열 출력 
			count++;
			System.out.println("#" + count + " " + Arrays.toString(data));
			
			return;
		}
		
		// i 번째 원소를 뽑는다.
		for (int i = 0; i < n; ++i) {
			
			// 이미 뽑힌 원소는 뽑지 않는다.
			if ((mask & 1 << i) != 0) continue;
			
			data[index] = input.get(i);
			permutation(index + 1, mask | 1 << i);
		}
	}
	
	public static void main(String[] args) throws Exception {
		System.out.println("nPr 출력 프로그램");
		
		// 수열 입력
		System.out.print("수열 입력: ");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		while (st.hasMoreTokens()) {
			input.add(Integer.parseInt(st.nextToken()));
		}
		
		// r 입력 및 변수 초기화
		System.out.print("r 입력: ");
		r = Integer.parseInt(br.readLine());
		
		n = input.size();
		data = new int[r];
		
		permutation(0, 0);
	}
}

• 이정도 만으로 거의 모든 순열이 필요한 상황을 구현할 수 있습니다.

java에서 순열 코드 틀을 기억하고 있을 필요성

• python으로 코딩을 할 때는 순열 코드를 어떻게 작성하는지 기억하고있을 필요성을 느끼지 못했습니다.
• itertools 라는 아주 멋진 모듈이 순열, 조합을 아주 간단하게 지원해주었거든요.

from itertools import permutations

nums = [1, 2, 3, 4, 5]

# permutations(nums, 3) : nums 리스트에서 3개를 뽑아 순열을 구성
for p in permutations(nums, 3):
    print(p)

• 하지만 java에는 python과 같이 순열을 간단히 지원해주는 내장 모듈이 존재하지 않습니다.
• 어려운 개념은 아니니 간단히 연습해보고 기억해놓으면 효율적인 코딩에 도움이 됩니다!