[JS] 순열

1. 순열

 순열은 서로 다른 n개의 원소에서 r개를 뽑아서 한 줄로 세우는 경우의 수를 말한다. 여기서 r,n은 자연수이며 r은 n이하여야만 한다.

또한 순열은 정의역과 공역이 같은 일대일 대응이다. 여기서 일대일 대응은 두 집합 사이를 중복 없이 모두 일대일로 대응시키는 함수를 말한다. 

 

[그림 1] 일대일 대응(출처: 전단사 함수, 위키백과)

 

 순열은 경우의 수이고 일대일대응이다. 왜 그런지 예를 한번 들어보자.

 앞에서 경우의 수에 대해서 이야기를 하지 않았는데, 경우의 수는 1회의 시행에서 일어날 수 있는 사건의 수를 말한다.

 

 

 아래 그림은 네 개의 문자를 가지고 있는 배열이 있는데, 네 개 중에 두 개의 문자를 임의로 골라 중복없이 조합하여 길이가 2인 단어를 생성하려고 하는 상황을 나타낸 것이다.

 

[그림 2] 4개의 문자를 가지고 길이 2인 단어를 조합해서 만드려고 한다.

 

 따라서 위의 예시를 보면, 두 개의 독립사건이 있는데, 첫 번째 독립사건은 배열의 첫 인덱스에 문자를 넣는 경우를 말하고, 두 번째 독립사건은 배열의 마지막 인덱스에 문자를 넣는 경우를 말한다. 따라서 두 독립사건은 동시에 일어나기 때문에 곱의 법칙이 성립된다.

 

 

 그래서 첫 번째 사건을 그림으로 나타내보면 다음과 같다.

 

[그림 1] 첫 번째 사건

 

 첫 번째 사건은 [A, B, C, D]라는 배열의 원소 하나를 골라 arr[0]에 대입하는 것이다. 그림 (a)에서는 네 가지 선택지 중에 B를 골라서 arr[0]에 담았다. 라는 것을 말해주고, 여기서 선택지가 네 개라는 것은 그림 (b)가 말을 해주는데, A, B, C, D 모두 arr[0]에 대입될 수 있기 때문에 첫 번째 사건은 일대일 대응이고 경우의 수는 4다.

 

 

 이번엔 두 번째 사건을 보자.

 

 

 두 번째 사건은 A, C, D 세 가지 선택지가 있다. 왜냐하면 B를 이미 골랐기 때문이다. 그림 (a)에서는 세 가지 선택지 중에 C를 고른 상황을 말하고, 그림 (b)는 A, C, D 모두 arr[1]에 대입될 수 있다는 것을 말한다. 따라서 두 번째 사건 역시 일대일대응이고 경우의 수는 3이다.

 

 

 두 사건은 독립적이고, 동시에 발생하기 때문에 곱의 법칙이 성립된다. 따라서 총 경우의 수는 4에서 3을 곱한 12가 되며, 이는 $$ _{4}P_{2} $$ 

 로 나타낼 수 있고, 이를 k 순열이라고 한다.

 

 

 k 순열은 서로 다른 n개의 원소 가운데 k개를 골라 순서 있게 나열한 것을 의미하고

 $$ _{n}P_{k} $$ 

 라고 표기하고, 다음과 같이 하강 계승으로 주어진다.

$$ _{n}P_{k} = n\times (n-1) .... \times(n-k+1) $$

 

 

 따라서 위 예제의 경우 n=4, k=2이므로

$$ _{2}P_{4} = 4\times (4-2+1) = 4\times 3 = 12$$

 가 된다.

 

 

 정말 경우의 수가 맞는지 확인해 보기 위해 단어를 한번 만들어 보았다.

 

 

AB, AC, AD

BA, BC, BD

CA, CB, CD

DA, DB, DC

 

 

단어의 총 개수는 12개이므로, 경우의 수인 12와 일치하므로 12개가 맞다.

 

2 . 프로그래밍 코드

이를 코드로 짤 경우 반복문을 사용하면 길이가 짧을 경우 괜찮지만, 길 경우에는 돌이킬 수 없는 시간복잡도를 볼 수 있을 것이다.

따라서 재귀호출을 이용할 것을 권장한다. 코드는 다음과 같다.

const input = ["A", "B", "C", "D"];
const answer = [];

const solution = (arr, n, k) => {
  if(n === arr.length-1){
    const str = arr.slice(0,k).join("");
    if(!answer.includes(str))
      answer.push(str);
    return;
  }
  else{
    for(let i=n; i<arr.length; i++){
      let temp = arr[n];
      arr[n] = arr[i];
      arr[i] = temp;

      solution(arr, n+1, k);

      arr[i] = arr[n]; 
      arr[n] = temp;
    }
  return answer;
  }
};

console.log(solution(input, 0, 2));

 

3. 참고 자료

1. 유튜버 수악중독님의 강의 - 순열

2. 위키백과 - 순열

3. 수학방님의 블로그 - 일대일 대응, 일대일함수, 항등함수

4. siyoon210 님의 블로그 - 순열(permutation) 알고리즘