[알고리즘] JS 조합, 순열 재귀함수 이해하기

순열과 조합, javascript 재귀함수 이해하기

완전탐색 문제풀이를 위해 조합과 순열을 공부했는데, 코드의 흐름이 이해가 잘 가지 않았다.

이전에 재귀함수를 학습할 때도 어렵다고 느꼈는데, forEach문까지 합쳐져서 더 헷갈렸던 것 같다.

재귀함수 + 반복문 어택으로 자꾸 스택의 흐름을 놓치게돼서 헷갈렸는데,

직접 그려보고, 디버거에 쌓이는 호출스택과 비교하면서 보니 코드가 이해되기 시작했다.

 

우선 조합과 순열에 대해서는 인터넷에 많은 자료가 있기 때문에 이 글에서는 최소한의 설명만 하고,

코드의 진행 방향에 대해서 설명하려고한다.

조합

const getCombinations = function (arr, selectNumber) {
	const results = [];
	if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return

	arr.forEach((fixed, index, origin) => {
		const rest = origin.slice(index + 1); // 해당하는 fixed를 제외한 나머지 뒤
		const combinations = getCombinations(rest, selectNumber - 1); // 나머지에 대해서 조합을 구한다.
		const attached = combinations.map((combination) => [fixed, ...combination]); //  돌아온 조합에 떼 놓은(fixed) 값 붙이기
		results.push(...attached); // 배열 spread syntax 로 모두다 push
	});

	return results; // 결과 담긴 results return
};

const example = [1, 2, 3, 4];
const result = getCombinations(example, 3);
console.log(result);

위 코드는 내부의 재귀함수가 종료조건에 도달할 때 까지, 재귀한다.

재귀함수가 종료되면, forEach문을 실행한다.

또다시 forEach문에서 재귀함수가 실행된다. 재귀함수를 종료조건에 도달할 때 까지 재귀한다.

재귀함수가 종료되면, forEach문을 실행한다.

....

초반의 스택 흐름은 위의 그림과 같다.

getCombination()의 재귀 종료 조건은, selectNum === 1 이다.

따라서 재귀함수를 계속해서 호출하다가, selectNum === 1 이 되는 순간,

const getCombination = function([3,4],1){
	const results = [];
	if (selectNumber === 1) return arr.map((value) => [value]); //[[3],[4]]
    ...하략
}

return = [[3],[4]] 을 갖고,  스택에서 pop된다.

forEach문 내에서 const combinations = [[3],[4]] 라는것을 알게되었다.

드디어 재귀가 종료되고 아래의 코드가 실행된다.

const getCombinations = function (arr, selectNumber) {
	const results = [];
	if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return

	arr.forEach((fixed, index, origin) => {
		const rest = origin.slice(index + 1); 
		const combinations = getCombinations(rest, selectNumber - 1); //재귀 종료! [[3],[4]]
		const attached = combinations.map((combination) => [fixed, ...combination]); //  돌아온 조합에 떼 놓은(fixed) 값 붙이기
		results.push(...attached); // [[2,3],[2,4]]
	});

	return results; // 결과 담긴 results return
};

재귀가 종료되면, forEach문을 마저 돌아야한다는 사실을 잊지 말자!

origin 배열이 [2,3,4]인 경우, forEach로 각각 2,3,4를 모두 순회해주어야한다.

방금 0번째 인덱스를 돌았으니 이번엔 1번째 인덱스를 돌 차례이다.

단, 여기에서 selectNum 은 빨간표시가 된 forEach가 생성된 getCombination([2,3,4],2)에서 참조하므로 (클로저 개념)

combinations = getCombinations([2,3,4], 2 -1) 가 된다.

즉 selectNum === 1 로, 재귀 종료조건에 해당하므로, [[4]]를 리턴하면서 재귀함수가 종료된다.

const combination = [[4]]로 재귀가 종료되었으니, 아래의 코드도 진행된다.

const getCombinations = function (arr, selectNumber) {
	const results = [];
	if (selectNumber === 1) return arr.map((value) => [value]); // [[4]]
	arr.forEach((fixed, index, origin) => {
		const rest = origin.slice(index + 1); // 
		const combinations = getCombinations(rest, selectNumber - 1); // 
		const attached = combinations.map((combination) => [fixed, ...combination]); //  [[3,4]]
		results.push(...attached); // [[2,3],[2,4],[3,4]]
	});

	return results; // 결과 담긴 results return
};

재귀가 종료되면 forEach문을 마저 돌아야한다. 벌써 지겨울 수 있음 주의;

방금 1번째 인덱스를 돌았으니 2번째 인덱스를 돌아야한다.

여기서도 마찬가지로 클로저 내부의 로컬변수들을 참조하기 떄문에 selectNum 이 1이 되어 재귀가 종료된다.

드디어 forEach문이 끝났다 ㅠㅠ

드디어 스택 하나를 pop했다 ㅠㅠㅠㅠ 감동..

combinations = [[2,3],[2,4],[3,4]]인 것을 알게 된 우리는 이하의 attached와 result.push()를 실행할 수 있게되었다.

result = [[1,2,3],[1,2,4],[1,3,4]] 가 된다.

끝이 아니지롱 ㅎㅎ... 다음 forEach문 요소를 반복하고, 재귀함수가 호출되고..끝이 없어보이는 반복이 시작된다.

그래도, 계속 같은 내용의 반복이기 때문에 더이상의 설명은 불필요할 것 같다.

결국 이런식으로 반복하다가 모든 스택이 pop되고 리턴되는값이 주어진 배열의 조합이된다.

---

이렇게 알고보면 쉽지만

머리로만 따라가기에는 계속 스택이 쌓였다가 사라졌다가를 여러번 반복하기 떄문에 쉽지 않다..

그럴 땐 역시 손으로 그려가면서 따라가는게 가장 쉬운 것?? 같다.

 

순열

순열은 여기서 rest의 조건만 변경하면 된다.

조합의 경우 순서가 상관없고, 순열의 경우 순서가 달라지면 다른 것으로 판단한다.

따라서 조합을 구할 때에는 아래의 알고리즘으로 구하게된다.

[1,2,3,4] 중 3개의 조합 구하기
- 1을 고정하고, [2,3,4]에서 2개 고를 수 있음. // [1]
    - 2를 고정하고 [3,4]에서 1개 고를 수 있음. // [1,2,3],[1,2,4]
    - 3을 고정하고 [4]에서 1개 고를 수 있음. // [1,3,4]
....

그러나 순열을 구할 때에는 순서가 다르면 다른 경우라고 판단하기 떄문에

아래의 알고리즘으로 구하게된다.

[1,2,3,4] 중 3개의 순열 구하기
- 1을 고정하고 [2,3,4]에서 2개 고를 수 있음 // [1]
    -2를 고정하고 [3,4]에서 1개 고를 수 있음 // [1,2,3],[1,2,4]
    -3을 고정하고 [2,4]에서 1개 고를 수 있음 // [1,3,2],[1,3,4]
    -4를 고정하고 [2,3]에서 1개 고를 수 있음 // [1,4,2],[1,4,3]

조합의 경우 : rest = 현재 인덱스 다음부터 끝까지
순열의 경우 : rest = 0~현재인덱스 + 현재인덱스 다음부터~끝까지

이를 코드로 보면 아래와 같다.

조합 rest = origin.slice(index + 1);
순열 rest = [...origin.slice(0, index), ...origin.slice(index + 1)];

결론적으로, 조합과 순열은 rest 코드만 차이가 있고, 나머지는 전부 똑같다.

 

Ref

https://jun-choi-4928.medium.com/javascript%EB%A1%9C-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-21df4b536349

JavaScript로 순열과 조합 알고리즘 구현하기

https://youngban.tistory.com/58

Recursion 이해하기(Javascript) 번역 및 요약