순열 (Permutation) [nPm]
- 서로 다른 n개의 물건 중에서 m개를 택하여 한 줄로 배열하는 것
- 순서가 있는 정렬을 만드는 경우의 수
예시)
[a,b,c]배열 내의 요소 모두를 줄 세우는 방법
[a,b,c], [a,c,b], [b,a,c], [b,c,a], [c,a,b], [c,b,a]
총 3! (=6개의) 경우의 수가 있음
구현하기
어떤 배열이 주어질 때, 배열 내의 원소들의 순열조합을 반환하는 함수를 구해보자
먼저 순열을 나열하기 위해서는 순차적으로 [a,b,c] 중에서 첫번째로 오는 원소를 선택하고, 그 이후 두번째 오는 원소를 나머지 원소중에서 선택해야 한다. 이후 세번째 오는 원소는 남아있는 원소중 하나를 선택해야한다.
순열을 만드는 자연스러운 방법속에서는 재귀적으로 한 행동이 반복되는 것을 확인할 수 있다.
배열 중 한 원소를 뽑고, 그 이후 나머지 원소들이 다음 뽑힐 수 있는 후보로 넘겨주는 것
잔여 배열에 원소를 하나씩 조회하면서 선별 배열에 둔다. (남겨진 잔여배열을 초기에 원본배열이라고 생각하면 규칙이 보일 것이다)
빨간색 네모로 표시한 1, 2, 3은 같은 로직이 반복되고 있다. 이것을 재귀함수로 구현할 수 있다.
종료조건은 잔여 배열의 길이가 0이거나, 선별 배열의 길이가 원본배열과 같을때 종료한다.
수도코드
- 선별 배열은 빈 배열, 잔여배열을 원본배열로 생각한다.
- 잔여배열내의 원소를 하나씩 순회하면서
- 선별 배열에서 조회된 원소를 넣는다.
- 잔여배열은 선별된 원소가 제외된 잔여배열로 다시 설정한다.
- 1~2의 과정을 하나의 재귀함수로 만들어서 호출한다. 이때 새로운 선별배열, 잔여배열을 인자로 받는다.
- 만약 종료조건에 해당하게 된다면 재귀호출을 종료하고, 조회가 가능하도록 ouput을 따로 기록한다.
1. 선별 [a] 잔여 [b,c]
1-1. 선별 [a,b] 잔여 [c]
1-1-1. 선별 [a,b,c] 잔여 [] => 순열 하나 완성
1-2. 선별 [a,c] 잔여 [b]
1-2-1. 선별 [a,c,b] 잔여 [b] => 순열 둘 완성
2. 선별 [b] 잔여 [a,c]
2-1. 선별 [b,a] 잔여 [c]
2-1-1. 선별 [b,a,c] 잔여 => 순열 셋 완성
2-2. 선별 [b,c] 잔여 [a]
2-2-1. 선별 [b,c,a] => 순열 넷 완성코드
const permutation = (permu, rests, output) => {
if (rests.length === 0) return output.push(permu);
rests.forEach((v, idx) => {
const rest = [...rests.slice(0, idx), ...rests.slice(idx + 1)]
permutation([...permu, v], rest, output);
})
}
const output = [];
permutation([], ['a', 'b', 'c'], output);
rest= 잔여배열
permu= 선별배열
응용
만약 원소를 모두 나열한 것이 아닌, 특정 n개의 원소 순열을 구하고 싶다면,
위 코드에서 종료조건을 수정하면 된다.
종료조건이 rests.length === 1 인경우, 잔여배열이 1이 되면 재귀함수를 멈추기때문에 전체 배열의 길이 3-1에 해당하는 길이의 순열을 얻을 수 있다.
조합 (Combination) [nCm]
- 서로 다른 n개의 물건에서 순서를 생각하지 않고 m개를 선택하는 것
- 순서가 없는 정렬을 만드는 경우의 수
예시) [a,b,c] 배열 내의 요소 모두를 줄 세우는 방법
[a,b,c], [a,c,b], [b,a,c], [b,c,a], [c,a,b], [c,b,a] 를 모두 같은 경우의 수로 본다.
총 1개 경우의 수가 있음
이전 순열 코드에서 한 부분만 변형 시켜주면 간단하게 구현할 수 있다.
차이는 잔여 배열을 남기는 방법에 있다.
-
순열
[a,b,c]배열이 있을 경우,a를 선택하면[b,c,d]가 잔여배열로 남고,b를 선택하면[a,c,d]가 잔여배열로 남는 방식으로 이전 잔여배열에서 선택한 것만 제거한 배열을 남긴다. -
조합
[a,b,c]배열이 있을 경우,a를 선택하면[b,c,d]가 잔여배열로 남고,b를 선택하면[c,d]만을 잔여배열로 남긴다.
이렇듯 조합은 순서가 중요하지 않기 때문에, b를 뽑은 조합의 경우
a를 잔여배열로 남기지 않을 경우[a,b,c]와[b,a,c]등에 중복된 경우에 수를 제거할 수 있다.
수도코드
- 선별배열은 빈배열, 잔여배열을 원본 배열로 생각한다.
- 잔여배열 내의 원소를 하나씩 순회하면서
- 선별 배열에 조회된 원소를 넣는다.
- 잔여배열을 선별된 원소의 인덱스 뒷 부분을 잔여배열로 설정한다.
- 1~2의 과정을 하나의 재귀함수로 만들어서 호출한다. 이때 새로운 선별배열, 잔여배열을 인자로 받는다.
- 만약 종료조건에 해당하게 된다면 재귀호출을 종료하고, 조회가 가능하도록 ouput을 따로 기록한다.
코드
const combination = (comb, rests, output) => {
if (comb.length === 0) return output.push(comb);
rests.forEach((v, idx) => {
const rest = rests.slice(idx + 1);
combination([...comb, v], rest, output);
});
}
const output = [];
combination([], ['a', 'b', 'c'], output);