[JS] 조합,순열,부분집합, 완전탐색

🧩 조합

• nCr, 서로다른 n개 중 r개 선택하되 순서를 안따짐
• 1,2,3 이랑 3,2,1 이랑 같은걸로 취급
• 코드

const getCombinations = function (arr, selectNumber) {
	const results = [];
  	// 배열 중 1개를 선택하는 경우 모든 요소를 1개짜리 배열에 담아 return
  	if (selectNumber === 1) return arr.map((value) => [value]);
	
  	// 1) 한 요소를 fixed한 후 나머지를 조합해서 붙인다.
    arr.forEach((fixed, index, origin) => {
       	// 2) fixed를 제외한 나머지 배열 구하기
      	const rest = origin.slice(index + 1);
      	// 3) 나머지 배열을 조합하기
      	const combinations = getCombinations(rest, selectNumber - 1);
      	// 4) fixed와 나머지 조합 합치기
      	const attached = combinations.map((combination) => [fixed, ...combination]);
      	// 합친 조합을 배열에 추가
      	results.push(...attached); 
    });

  	return results;
}

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

🧩 순열

• nPr, 서로다른 n개 중 r개 선택하되 순서를 따짐
• 1,2,3 이랑 3,2,1 이랑 다른걸로 취급
• 코드

const getPermutations= function (arr, selectNumber) {
  	const results = [];
  	// 배열 중 1개를 선택하는 경우 모든 요소를 1개짜리 배열에 담아 return  
  	if (selectNumber === 1) return arr.map((value) => [value]); 
  
	// 1) 한 요소를 fixed한 후 나머지를 순열로 세운다.
  	arr.forEach((fixed, index, origin) => {
      
    // 2) fixed를 제외한 나머지 배열 구하기
    const rest = [...origin.slice(0, index), ...origin.slice(index+1)]
    // 3) 나머지 배열로 순열세우기
    const permutations = getPermutations(rest, selectNumber - 1);
    // 4) fixed와 나머지 순열 합치기
    const attached = permutations.map((permutation) => [fixed, ...permutation]); // 돌아온 순열에 대해 떼 놓은(fixed) 값 붙이기
    // 5) 합친 순열을 배열에 추가
    results.push(...attached);
  });

  return results;
};

const example = [1,2,3,4];
const result = getPermutations(example, 3);
// [[1, 2, 3],[1, 2, 4],[1, 3, 2],[1, 3, 4],[1, 4, 2],[1, 4, 3],[2, 1, 3],[2, 1, 4],[2, 3, 1],[2, 3, 4],[2, 4, 1], ... [4, 3, 2]

🧩 부분집합

• n개중 몇개를 뽑든 모든 경우의 수를 구함. 단, 순서를 안따짐

[1,2,3] 의 부분 집합

[1],[2],[3],[1,2],[2,3],[1,3],[1,2,3]

• 코드

let arr = [1,2,3,4];
let result = [];

for(let i = 1; i < (1 << arr.length); i++) {
  	result.push([]);
	for(let j = 0; j < arr.length; j++) {
    	if(i & (1 << j)) result[i-1].push(arr[j])
    }
}

console.log(result);
// [[1],[2],[1, 2],[3],[1, 3],[2, 3],[1, 2, 3],[4],[1, 4],[2, 4],[1, 2, 4],[3, 4],[1, 3, 4],[2, 3, 4],[1, 2, 3, 4]]

🧩 완전탐색

• n개중 몇개를 뽑든 모든 경우의 수를 구함. 단, 순서를 따짐

[1,2,3] 의 완전탐색

[1],[2],[3],
[1,2],[2,1],[2,3],[3,2],[1,3],[3,1],
[1,2,3],[2,1,3],[2,3,1]...

• 코드

let set = new Set();
numOfCase([1,7],'')
function numOfCase(arr,str) {
	if(arr.length) {
    	for(let i = 0; i <arr.length; i++) {
        	let copy = [...arr];
          	copy.splice(i,1);
          	numOfCase(copy,str + arr[i])
        }
    }
  	if(str > 0) set.add(Number(str))
}
console.log(Array.from(set))  // [17, 1, 71, 7]

---

출처

• https://velog.io/@min00/JS-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89-Exhaustive-Search-%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EB%B6%80%EB%B6%84%EC%A7%91%ED%95%A9