[javascript] 순열, 조합, 중복순열, 중복조합
순열, 조합
순열과 조합은 서로 다른 n개에서 r개를 선택한다는 부분에서 동일하다. 그러나 순열은 동일한 아이템을 다른 순서로 선택하는 경우 다른 경우의 수로 보지만 조합은 동일한 아이템을 다른 순서로 선택하여도 동일한 경우의 수로 본다. 즉, 순열은 순서를 상관하지만 조합은 순서를 상관하지 않는다.
예를 들어 [a, b, c, d, e]에서 3개를 선택할 경우 순열은 [a,b,c]와 [a,c,b]를 다른 경우의 수로 보지만 조합은 동일한 것으로 간주한다.
javascript에서 순열과 조합을 구하는 기본 프로세스는 동일하다. 재귀 함수를 이용해 i번째 자리에 선택할 수 있는 아이템들을 for문으로 탐색하고, i+1번째에 선택할 수 있는 아이템의 범위를 추려 다음 재귀의 매개변수로 전달해준다. i가 선택하고자 하는 아이템의 개수와 동일할 경우 재귀를 종료한다.
이때 다음 자리에 올 수 있는 아이템 범위를 추리는 방법에서 순열과 조합의 차이가 나타난다. 순열은 현재 방문한 i번째 아이템을 제외한 나머지 아이템들이 다음 자리에 올 수 있지만, 조합은 현재 방문한 i번째 아이템 뒤의 아이템들만 다음 자리에 올 수 있다. 조합에서는 [i-1, i]과 [i, i-1]이 동일한 경우의 수이므로 현재 아이템보다 앞서 선택했던 아이템은 다시 선택할 필요가 없기 때문이다.
따라서 순열에서는 현재 i번째 아이템을 제외한 나머지 아이템으로 배열을 재구성해 재귀의 매개변수로 전달해주고, 조합에서는 현재 인덱스의 다음 순서 i+1을 재귀의 매개변수로 전달한다.
순열
순열을 구하는 다른 방법 중 원본 배열인 list의 아이템들의 위치를 교환해주며 경우의 수를 구하는 방법도 있다. 방문한 아이템들을 담는 임의의 변수를 생성하지 않아도 돼 공간 복잡도 면에서 효율적이다.
조합
중복 순열, 중복 조합
중복 순열과 중복 조합은 동일한 아이템을 2회 이상 선택할 수 있는 경우이다. [a, b, c, d, e]의 아이템들 중에서 3개를 선택해 중복 순열이나 중복 조합을 만들 경우[a, a, a]와 같은 경우가 허용되는 것이다.
사전에서 단어를 순서대로 나열하는 경우는 중복 순열, 1점부터 10점까지 있는 과녁에 n개의 화살을 쏠 경우의 수는 중복 조합이다.
중복 순열과 중복 조합은 i+1번째에 추가할 아이템의 범위 추릴 때 i번째 아이템도 포함한다. 그러나 중복 순열은 0부터 i-1까지 이전에 선택했던 모든 아이템들을 범위에 포함하지만 중복 조합은 이전에 선택했던 아이템들은 제외한다. 이는 재귀 함수 내에서 for 문의 범위를 중복 순열은 전체 범위로, 중복 조합은 현재 인덱스 i로 설정해주면 된다.
