순열/조합 찾기 알고리즘: Next Permutation

1. 순열

C++에서 다음 순열을 찾으려면 SLT 알고리즘에 있는 next_permutation 함수를 사용하면 된다. next_permutation의 시간 복잡도는 O(n)이다. 그러나 다른 언어에는 없기 때문에 직접 구현하면서 구조를 알아보려 한다. 

다음과 같은 순서로 다음 순열을 찾게된다.

 

1. a[i] < a[i+1]를 만족하는 i 중에 가장 큰 수를 찾는다. (만약 i가 없다면 그 순열은 마지막 순열이다.)
2. a[j] > a[i]를 만족하는 가장 큰 j를 찾는다. (j > i)
3. a[i] 와 a[j]를 swap한다.
4. a[i+1]부터 reverse 해준다.

이것을 Javascript로 구현하면 다음과 같다.

// n = 배열의 length
let index = -1;
for(let i = n-2; i >= 0; i--){  //1. a[i] < a[i+1]를 만족하는 i 중에 가장 큰 수를 찾는다.
  if(num[i] < num[i+1]){ 
    index = i;
    break;
  }
}
if(index < 0){
	break; //1. (만약 i가 없다면 그 순열은 마지막 순열이다.)
} else {
  for(let i = n-1; i > index; i--){
    if(num[i] > num[index]){  // 2. a[j] > a[i]를 만족하는 가장 큰 j를 찾는다.
      const temp = num[i]; // 3. a[i] 와 a[j]를 swap한다.
      num[i] = num[index];
      num[index] = temp;
      break;
    }
  num = [...num.slice(0, index+1), ...num.slice(index+1).reverse()]; // 4. a[i+1]부터 reverse 해준다.
  console.log(num);
}

이전 순열 (prev_permutation)을 구할 때는 동일한 순서이지만 비교할 때 부등호만 반대로 해주면 된다.

let index = -1;
for(let i = n-2; i >= 0; i--){  //1. a[i] > a[i+1]를 만족하는 i 중에 가장 큰 수를 찾는다.
  if(num[i] > num[i+1]){ 
    index = i;
    break;
  }
}
if(index < 0){
	break; //1. (만약 i가 없다면 그 순열은 마지막 순열이다.)
} else {
  for(let i = n-1; i > index; i--){
    if(num[i] < num[index]){  // 2. a[j] < a[i]를 만족하는 가장 큰 j를 찾는다.
      const temp = num[i]; // 3. a[i] 와 a[j]를 swap한다.
      num[i] = num[index];
      num[index] = temp;
      break;
    }
  num = [...num.slice(0, index+1), ...num.slice(index+1).reverse()]; // 4. a[i+1]부터 reverse 해준다.
  console.log(num);
}

모든 순열을 구할 때에는 do~while을 사용해서 구할 수 있다. 주의할 점은 만약 처음에 주어진 순열이 정렬이 되어있지 않은 상태라면 정렬을 해주어야 한다. 왜냐하면 해당 알고리즘은 더 큰 순열을 찾아주기 때문에 만약에 순열의 앞부분이 큰 숫자로 되어있다면 작은 순열을 찾아주지 않는다.

let index;
num = num.sort((a,b) => a-b); // 오름차순으로 정렬하기
do{
  console.log(num);
  index = -1;
  for(let i = n-2; i >= 0; i--){  //1. a[i] < a[i+1]를 만족하는 i 중에 가장 큰 수를 찾는다.
    if(num[i] < num[i+1]){ 
      index = i;
      break;
    }
  }
  if(index < 0){
      break; //1. (만약 i가 없다면 그 순열은 마지막 순열이다.)
  } else {
    for(let i = n-1; i > index; i--){
      if(num[i] > num[index]){  // 2. a[j] > a[i]를 만족하는 가장 큰 j를 찾는다.
        const temp = num[i]; // 3. a[i] 와 a[j]를 swap한다.
        num[i] = num[index];
        num[index] = temp;
        break;
      }
    }
    num = [...num.slice(0, index+1), ...num.slice(index+1).reverse()]; // 4. a[i+1]부터 reverse 해준다.
  } 
} while(index >= 0)

2. 조합

n개의 원소를 가진 순열 중 k개를 사용해서 조합을 구할 때에는, n개의 원소를 가진 배열을 하나 만들고 그중에 k 개는 1로 나머지는 0으로 초기화시켜준 다음 순열을 구할 때와 동일한 순서로 구현하되 답을 가져올 때는 새로운 배열에서 값이 1인 index들로만 순열에서 값을 가져오면 된다.

 

예를 들어 순열이 [1, 3, 5, 7, 9]라 할 때 숫자 3개의 조합을 구한다고 하면 새로운 배열 [0, 0, 1, 1, 1]을 만들고 배열 중 1인 부분만 답으로 가져오면 된다: [5, 7, 9]

let index;
let flag = [];   //새로운 배열 만들기
const output = [];
for(let i = 0; i < n; i++){ // 새로운 배열의 길이는 n이고 k만큼만 1로 나머지는 0으로 초기화 
  flag[i] = 1;
  if(i > k){
    flag[i] = 0;
  }
}
flag = flag.sort((a,b)=>a-b);
do{
  index = -1;
  output.push(num.filter((e, i) => flag[i] == 1)); //새로운 배열에서 1에 해당하는 값만 가져오기
  for(let i = n-2; i >= 0; i--){
    if(flag[i] < flag[i+1]){
      index = i;
      break;
    }
  }
  if(index < 0){
  	break;
  } else {
    for(let i = n-1; i > index; i--){
      if(flag[i] > flag[index]){                    
        const temp2 = flag[i];
        flag[i] = flag[index];
        flag[index] = temp2;
        break;
      }
    }
  flag = [...flag.slice(0, index+1), ...flag.slice(index+1).reverse()];
  }
} while(index >= 0)