Next Permutation

Next Permutation

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

알고리즘

• 배열을 오름차순으로 정렬한 후 시작한다.
• 아래 과정을 반복하여 사전 순으로 다음으로 큰 순열 생성(가장 큰 내림차순 순열을 만들 때까지 반복한다.)

1. 뒤쪽부터 탐색하며 교환 위치(i - 1)찾기 (i : 꼭대기)
2. 뒤쪽부터 탐색하며 교환 위치(i - 1)와 교환할 큰 값 위치(j) 찾기
3. 두 위치 값(i - 1, j) 교환
4. 꼭대기 위치(i)부터 맨 뒤까지 오름차순 정렬

주의사항

Next Permutation 사용 전에 숫자 배열을 오름차순으로 정렬하여 가장 작은 순열 한번 처리

구현 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
    static int[] input;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        input = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; ++i){
            input[i] = Integer.parseInt(st.nextToken());
        }

        // 반드시 사전순으로 정렬을 한 후, nextPermutation 호출
        Arrays.sort(input);

        do {
            System.out.println(Arrays.toString(input));
        }while (nextPermutation());

        br.close();
    }
    static boolean nextPermutation(){
        int i = input.length - 1;
        int j = input.length - 1;
        int k = input.length - 1;

        // i-1 찾기
        while (i > 0 && input[i-1] >= input[i]){
            --i;
        }
        if(i == 0) return false;

        // j 찾기
        while (input[i-1] >= input[j]) --j;

        // i-1, j swap
        swap(i-1, j);

        // i 보다 뒤에 있는 부분은 오름차순으로 정렬
        while (i < k){
            swap(i++, k--);
        }
        return true;
    }
    static void swap(int i, int j){
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }
}
/**
 *  입력
 *  3
 *  2 3 1
 */

/**
 *  출력
 *  [1, 2, 3]
 *  [1, 3, 2]
 *  [2, 1, 3]
 *  [2, 3, 1]
 *  [3, 1, 2]
 *  [3, 2, 1]
 */

Next Permutation을 이용한 조합

• 원소 크기와 같은 크기의 int 배열 P를 생성하여 r개 크기만큼 뒤에서 0이 아닌 값(예를 들어 1)으로 초기화 한다.
• nextPermutation 알고리즘을 활용한다.
• nextPermutation 알고리즘 한 번 수행 시마다 조합이 만들어짐
  => nextPermutation 과정 수행 시마다 0이 아닌 값의 위치가 변경됨
• P 배열에서 0이 아닌 값을 갖고 있는 위치에 해당하는 원소가 조합에 선택된 것임

구현 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
    static int[] input;
    static int[] P;
    static int N, R;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb;

        N = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        input = new int[N];
        P = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; ++i){
            input[i] = Integer.parseInt(st.nextToken());
        }

        // 반드시 사전순으로 정렬을 한 후, nextPermutation 호출
        Arrays.sort(input);
        
        // 4C2 인 경우 배열의 2, 3 인덱스를 0이 아닌 값으로 변경
        for(int i = R; i < N; ++i)
            P[i] = 1;

        do {
            sb = new StringBuilder();
            // P가 1인 인덱스의 input만 출력
            for(int i = 0; i < N; ++i){
                if(P[i] == 1) sb.append(input[i]).append(" ");
            }
            System.out.println(sb.toString());
        }while (nextPermutation());

        br.close();
    }
    static boolean nextPermutation(){
        int i = P.length - 1;
        int j = P.length - 1;
        int k = P.length - 1;

        // i-1 찾기
        while (i > 0 && P[i-1] >= P[i]){
            --i;
        }
        if(i == 0) return false;

        // j 찾기
        while (P[i-1] >= P[j]) --j;

        // i-1, j swap
        swap(i-1, j);

        // i 보다 뒤에 있는 부분은 오름차순으로 정렬
        while (i < k){
            swap(i++, k--);
        }
        return true;
    }
    static void swap(int i, int j){
        int temp = P[i];
        P[i] = P[j];
        P[j] = temp;
    }
}
/**
 *  입력
 *  4 2
 *  2 3 1 4
 */

/**
 *  출력
 *  3 4 
 *  2 4 
 *  2 3 
 *  1 4 
 *  1 3 
 *  1 2 
 */

시간복잡도