순열 알고리즘

[ 알고리즘 ]

1. 배열 P에서 P[X] < P[X+1]을 만족하는 가장 큰 인덱스 값 X 구하기
  ( 만약 X가 없다면 탐색 종료 )

 

2. 배열에서  P[X] < P[Y]를 만족하는 가장 큰 인덱스 값 Y 구하기

 

3. P[X]와 P[Y]의 값 교환하기

 

4. P[X+1] ~ P[N]까지의 값 뒤집기

 

[ 소스코드 ]

  boolean nextOrder() {
    int x, y;
    
    // 1. Find largest x such that P[x]<P[x+1]
    x = -1;
    for(int i=0;i<sz-1;i++) {
      if(num[i] < num[i+1]) x = i;
    }
    
    if(x == -1) return false;
    else {
      // 2. Find largest y such that P[x]<P[y]
      y = 0;
      for(int j=0;j<sz;j++) {
        if(num[x] < num[j]) y = j;
      }
      
      // 3. Swap P[x] and P[y]
      SWAP(num, x, y);
      
      // 4. Reverse P[x+1:n]
      int l, r;
      l = x+1; r = sz-1;
      while(l<r) {
        SWAP(num, l, r);
        l++; r--;
      }
      
      return true;
    }
  }

 

참고

https://www.youtube.com/watch?v=goUlyp4rwiU&ab_channel=TheCodingTrain