# Exercise 4 - permutations
Write a function that takes in an empty array or an input array of an consecutive positive integers, starting at 1, and returns an array of all possible permutations of the original array
The integers will not repeat.
```javascript
permutations([1, 2, 3]); // [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// An empty set has a single permutation, 0! = 1
permutations([]); // [[]]
```
문제:
1부터 시작하여 연속된 정수로 이루어져 있거나 빈 배열이 주어질 때, 가능한 모든 순열로 이루어진 배열을 반환하는 함수를 작성하여라.
const permutations = function (input) {
};
풀이:
- base case
재귀함수는 우선 베이스케이스를 잘 잡아야 한다.
다시 호출되는 인자도 배열이기 때문에 베이스 케이스도 배열을 반환해야 한다.
우선 반환할 빈 배열을 하나 생성한다.
let answer = [];
첫 번째 테스트 케이스는 빈배열을 인자로 준다.
test("1 possible permutation for a set containing 0 numbers", () => {
expect(permutations([])).toEqual([[]]);
});
이경우 가능한 순열은 [] 하나밖에 없으므로 [[]] 을 리턴해야 한다.
if (input.length === 0) {
answer.push(input);
return answer;
}
두 번째 테스트 케이스의 인자는 값이 하나만 있는 배열이다.
test("1 possible permutation for a set containing 1 number", () => {
expect(permutations([1])).toEqual([[1]]);
});
마찬가지로, 가능한 순열조합은 하나밖에 없으므로 그대로 배열에 담아 반환한다.
if (input.length === 1) {
answer.push(input);
return answer;
}
내가 이해하기로 베이스케이스는 재귀가 멈추는 조건이다. 빈 배열이 인자로 주어지는 것은 예외케이스에 가까운 것 같고, 그보다 배열에 요소가 단 하나만 있을 때, 재귀를 멈추고 인자를 그대로 담은 배열을 반환하여 실제로 내용을 채워 간다는 것을 이해하고 나서야 풀이 방향을 알 것 같았다.
어쨌든 코드 생긴 건 비슷하니까 두 조건을 합치면
const permutations = function (input) {
let answer = [];
if (input.length <= 1) {
answer.push(input);
return answer;
}
return answer[];
};
베이스케이스는 완성된다.
- recursion call
예를 들어 input = [1, 2, 3] 일 때 [[3]] => [[2, 3]] => [[1, 2, 3]] 식으로 버블링 되어야 한다. 반대로 과정을 생각하면 [1, 2, 3]에서는 1이라는 요소를 빼고, [2, 3]에서는 다시 2를 빼고 하는 식으로 input의 각 요소를 순회하며 그 요소를 제외한 새로운 배열을 만들어야 하므로, 우선 해당 코드를 작성한다.
input.forEach((currentItem) => {
const restItems = input.filter((item) => item !== currentItem);
}
이 상태에서 restItems를 인자로 주는 permutations를 다시 호출하면 restItems.length === 1인 경우까지 호출된 후 [[3]]이 제일 먼저 반환될 것이고, 이때 input = [2, 3], currentItems = 2이다. 반환된 배열을 permutation이라고 하자
input.forEach((currentItem) => { // currentItem = 2
const restItems = input.filter((item) => item !== currentItem); // restItems = [3]
const permutation = pemutations(restItems); // permutation = [[3]]
}
하드코딩으로 일단 결과만 내보면 permutation[0]에 currentItem을 붙여줘야 한다. test코드에서 sort로 후처리가 있기 때문에 push하는게 성능면에서 이득이지만, 우선 알아보기 쉽게 unshift로 진행한다.
input.forEach((currentItem) => { // currentItem = 2
const restItems = input.filter((item) => item !== currentItem); // restItems = [3]
const permutation = pemutations(restItems);
permutation[0].unshift(curretItem); // permutation[0] = [2, 3], permutation = [[2, 3]]
}
그리고 permutatoin을 answer 에 담아주는데 둘 다 배열이므로 concat을 사용한다.
input.forEach((currentItem) => { // currentItem = 2
const restItems = input.filter((item) => item !== currentItem); // restItems = [3]
const permutation = pemutations(restItems);
permutation[0].unshift(curretItem); // permutation[0] = [2, 3], permutation = [[2, 3]]
answer = answer.concat(permutation) // answer = [[2, 3]]
}
currentItem이 3로 넘어간 후 같은 과정을 반복하면, input = [2, 3] 일 때 반환되는 answer = [[2, 3], [3, 2]]가 된다. 그 이전 호출로 돌아가면 currentItem = 1일 때 permutation = [[2, 3], [3, 2]]이다. 그런데 여기서 permutation[0]에만 currentItem을 붙이면 permutation = [[1, 2, 3], [3, 2]]이 된다. 이를 해결하기 위해 permutation의 각 요소를 순회하며 currentItem을 붙이게 코드를 수정한다.
input.forEach((currentItem) => { // currentItem = 1
const restItems = input.filter((item) => item !== currentItem); // restItems = [[2, 3]]
const permutation = pemutations(restItems); // [[2, 3], [3, 2]]
permutation.forEach((p) => p.unshift(currentItem)); // permutation = [[1, 2, 3], [1, 3, 2]]
answer = answer.concat(permutation) // answer = [[1, 2, 3], [1, 3, 2]]
}
curretItem이 2로 넘어간 후 restItems = [1, 3]으로 바꾸어 다시 같은 과정을 진행하면 permutations(restItems)은 [[1, 3], [3, 1]]을 반환한다. 여기에 curretItem을 붙이고 나면 permutation = [[2, 1, 3], [2, 3, 1]]을, answer에 concat 하면 answer = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]]이 된다. currentItem이 3으로 넘어가도 같은 방식으로 동작하여 최종적으로
answer = [
[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1]
];
이 된다.
test("6 possible permutations for a set containing 3 numbers", () => {
expect(permutations([1, 2, 3]).sort()).toEqual(
[
[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1],
].sort()
);
});
input을 [1, 2, 3, 4]로 바꾸어도 기대한대로 작동하였다.
