순열과 조합에 대해 배우기 앞서 경우의 수는 무엇일까?

ex) 월드컵 16강을 진출하기 위한 조별전 승점 필요 갯수, 대학교 진학을 위한 내신 등급 ...

변화에 따른 결과가 바로 경우의 수이다.

이처럼 경우의 수 결과를 나열하는데 있어 대표적인 알고리즘은 순열과 조합이다.

이번 시간에는 경우의 수에 대한 값을 도출하는 순열, 조합에 대해 알아보자.

순열

순열은 경우의 수 중 순서에 의존한 알고리즘이다.

function permutation(count) {
	count = count || 2;
	let result = [];
  	let stuffArr = [1, 2, 3];
  
  	let func = (arr, bucket, num) => {
    		if(num === 0) {
			return result.push(bucket)
		}
      
      		for(let i = 0; i < arr.length; i++) {
			let clone = arr.slice();
          		let cur = arr.splice(i, 1)
            
            		func(clone, bucket.concat(cur), num - 1)
		}
    	}
    
 	func(stuffArr, [], count)
  	return result
}

해석

1. 순열 알고리즘을 생성하기 위해 result 빈 배열을 생성한다.
2. 순열 메커니즘을 작동시킬 함수를 하나 별도로 생성한다.
3. bucket은 기존 stuffArr 배열의 요소를 담아줄 역할을 수행한다.
4. clone은 원본 배열 훼손을 방지하고자 생성하였으며 i 인덱스로 cur 현재 요소 할당하고 이는 bucket에 저장된다.
5. 재귀함수를 통해 bucket을 순차적으로 저장하고 재귀 베이스로 탈출할 경우 result 배열에 2차원 배열 형태로 저장한다.

Another type

function permutation(count) {
  
	count = count || 2
  	let results = [];
  	let stuffArr = [1, 2, 3]
    
  if (count === 1) {
  	return stuffArr.map((i) => [i]); 
  }
  
  stuffArr.forEach((fixed, index, array) => {
    const clone = array.slice();
    rest.splice(index, 1)
    const permutations = newChickenRecipe(clone, choiceNum - 1); 
    const attach = permutations.map((permutation) => [fixed, ...permutation]); 
    results.push(...attach); 
  });

  return results;
}

꼭 재귀함수를 사용해야하는가?

사실 재귀함수 없이 중첩 반복문을 활용하여 순열 알고리즘을 구현할 수 있다.

for(let i = 0; i < arr.length; i++) {
    for(let j = i + 1; j < arr.length; j++) {
      for(let k = j + 1; k < arr.length; k++) {
        result.push([arr[i], arr[j], arr[k]]);

      }
    }
  }

그러나 위의 방법은 순열을 표현하는데 3개의 요소만 저장할 경우 3개의 반복문을 활용한 것이다.

만일 극단적으로 1000개가 되는 요소면 1000개의 중첩 반복문이 필요하게 되는 경우로 인해 재귀함수가 용이하게 쓰인다.

중복 순열

중복 순열은 순서에 의존하며 중복 요소가 허용되는 알고리즘이다.

function permutation_repetition(count) {
	count = count || 2;
	let result = [];
  	let stuffArr = [1, 2, 3];
  
  	let func = (arr, bucket, num) => {
    		if(num === 0) {
			return result.push(bucket)
		}
      
      		for(let i = 0; i < arr.length; i++) {
			let clone = arr.slice();
            		let cur = arr[i]
            
            		func(clone, bucket.concat(cur), num - 1)
		}
    	}
   
    	func(stuffArr, [], count)
  	return result;
}

해석

1. result 빈 배열을 생성한다. (이는 순열, 조합 모두 공통적으로 배열을 저장해야하므로 같다.)
2. let cur = arr[i] 현 요소를 할당한다.
3. 재귀함수를 통해 clone 복사본이 훼손되지 않은채 중복된 요소가 연속적으로 들어간다.

Another type

function permutation_repetition(count) {
  let results = [];
  count = count || 2
  let arr = [1, 2, 3]
  
 
  if (count === 1) return arr.map((i) => [i]); 

  arr.forEach((fixed, index, array) => {
    const permutations = permutation_repetition(count - 1); 
    const attached = permutations.map((permutation) => [fixed, ...permutation]);
    results.push(...attached); 
  });

  return results;
}

조합

순서에 의존하지 않은 알고리즘

function combination(count) {
	count = count || 2;
	let result = [];
  	let stuffArr = [1, 2, 3];
  
  	let func = (arr, bucket, num) => {
    		if(num === 0) {
			return result.push(bucket)
		}
      
      		for(let i = 0; i < arr.length; i++) {
			let clone = arr.slice();
          		let cur = arr[i]
            
            		func(clone.slice(i + 1), bucket.concat(cur), num - 1)
		}
    	}
    
    	func(stuffArr, [], count)
  	return result
}

해석

1. result 빈 배열을 생성한다. (이는 순열, 조합 모두 공통적으로 배열을 저장해야하므로 같다.)
2. let cur = arr[i] 현 요소를 할당한다.
3. 재귀함수를 통해 clone은 순서에 의존하지 않으므로 slice 메서드로 부터 1씩 증가 시킨다.

Another type

function combination(arr = [1, 2, 3], count) {
  let results = [];
  count = count || 2
 
  if (count === 1) return arr.map((i) => [i]); 

  arr.forEach((fixed, index, array) => {
    const clone = array.slice(index + 1)
    const permutations = combination(clone, count - 1); 
    const attached = permutations.map((permutation) => [fixed, ...permutation]);
    results.push(...attached); 
  });

  return results;
}