Next Permutation (Java)

1. Algorithm

! 전제 조건 → 입력 배열의 오름차순 정렬 상태 !

1. i를 맨 뒤로 두어 앞으로 오며 탐색하며 (i - 1) 위치의 값이 i 위치의 값보다 작아지는 교환 위치 (i - 1) 찾기, 이 때, i 위치의 값을 꼭대기라 칭함

2. j를 맨 뒤로 두어 앞으로 오며 탐색하며 교환 위치 (i - 1)와 교환할 큰 값 (뒤쪽에서 처음으로 (i - 1) 위치의 값보다 커지는 수) 위치 j 찾기

3. 두 (i - 1), j 위치 값 교환

4. k를 맨 뒤로 두어 앞으로 오며 꼭대기 위치 i부터 맨 뒤까지 오름차순 정렬 (가장 작은 순열 형태로 변경)

2. Code

void swap(int[] numbers, int i, int j) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
}

boolean nextPermutation(int[] numbers) {
    int n = numbers.length;
    
    int i = n - 1;
    
    while (i > 0 && numbers[i - 1] >= numbers[i]) i--;
    
    if (i == 0) return false;
    
    int j = n - 1;
    
    while(numbers[i - 1] >= numbers[j]) j--;
    
    swap(numbers, i - 1, j);
    
    int k = n - 1;
    
    while(i < k) swap(numbers, i++, k--);
    
    return true;
}

3. Simulation Video

영상 내 오류 수정

np → nextPermutation
swap → 배열 내 두 인덱스의 값의 위치를 서로 바꿔주는 함수