파이썬에서는 라이브러리로 바로 사용할 수 있는 순열과 조합을 자바스크립트에서는 어떻게 구현할까요? 재귀를 사용하면 구할 수 있습니다 !!
JS를 이용한 순열, 조합 구현 방법을 공부하고, 알고리즘에 적용해 풀어봤습니다 😊
중복 없는 순열
주어진 배열 arr에서 필요한 개수만큼 뽑아 순서를 고려해서 나열하는 방법입니다.
같은 요소들로 구성되었어도 순서가 달라지면 다른 배열이 됩니다 !
function getPermutations(arr, selectNum) {
const permutations = [];
const permute = (tmp, remaining) => {
if (tmp.length === selectNum) {
permutations.push([...tmp]);
return;
}
for (let i = 0; i < remaining.length; i++) {
permute(
[...tmp, remaining[i]],
[...remaining.slice(0, i), ...remaining.slice(i + 1)]
);
}
};
permute([], arr);
return permutations;
}
const arr = [1, 2, 3, 4];
console.log(getPermutations(arr, 2));
getPermutations(주어진 배열, 필요한 개수)형태로 함수를 생성합니다.- getPermutations 안에서 재귀함수
permute(현재 만들어지는 중인 조합 배열, 남아있는 원래 배열)를 생성합니다.
2-1. 이때 필요한 개수만큼 숫자가 뽑히면if (tmp.length === selectNum)을 통해permutations에 해당 배열을 저장한 후permute함수를 종료합니다.
2-2. 아니라면 for문을 돌며 재귀함수를 호출하며 순열을 생성합니다. 이때 permute 함수에permute([현재까지 만들어진 배열 + 추가할 요소], [추가된 요소를 제외한 남은 배열])를 넘깁니다. 추가할 요소가 중간에 있을 수 있으니 해당 요소 직전까지 자른 배열 + 해당 요소 이후부터 전부로 잘라서 하나의 배열을 만듭니다.
필요한 개수가 될 때까지 재귀함수permute을 호출하고, 만들어진 순열을 permutations에 넘기고, 실행했던 permute들을 차례로 종료해가며 for문의 idx를 하나씩 증가시킵니다. 이렇게 배열을 전부 돌며 순열을 생성합니다. - for문이 종료되면
return permutations;을 통해 만들어진 순열들을 반환합니다.
혹시 이해가 잘 안되면 중간중간 console.log()를 찍어보며 흐름을 살펴보시길 추천합니다 !👍🏻
중복 없는 조합
주어진 배열 arr에서 필요한 개수만큼 뽑아 순서를 고려하지 않고 나열하는 방법입니다.
같은 요소들로 구성되었다면 순서가 달라도 같은 배열로 판단합니다.
function getCombinations(arr, selectNum) {
const combinations = [];
const combine = (tmp, startIdx) => {
if (tmp.length === selectNum) {
combinations.push([...tmp]);
return;
}
for (let i = startIdx; i < arr.length; i++) {
combine([...tmp, arr[i]], i + 1);
}
};
combine([], 0);
return combinations;
}
const arr = [1, 2, 3, 4];
console.log(getCombinations(arr, 2));
getCombinations(주어진 배열, 필요한 개수)형태로 함수를 생성합니다.- getCombinations 안에서 재귀함수
combine(현재 만들어지는 중인 조합 배열, 추가를 시작할 idx)를 생성합니다.
2-1. 이때 필요한 개수만큼 숫자가 뽑히면if (tmp.length === selectNum)을 통해combinations에 해당 배열을 저장한 후combine함수를 종료합니다.
2-2. 아니라면 for문을 돌며 재귀함수를 호출하며 조합을 생성합니다. 이때 combine함수에combine([현재까지 만들어진 배열 + 추가할 요소], 다음 startIdx)를 넘깁니다. 다음 idx는i + 1로 넘겨서 중복 선택을 방지합니다.
필요한 개수가 될 때까지 재귀함수combine을 호출하고, 만들어진 조합을 combinations에 넘기고, 실행했던 combine들을 차례로 종료해가며 for문의 idx를 하나씩 증가시킵니다. 이렇게startIdx부터 배열의 끝까지 조합을 생성합니다. - for문이 종료되면
return combinations;을 통해 만들어진 조합들을 반환합니다.
혹시 이해가 잘 안되면 중간중간 console.log()를 찍어보며 흐름을 살펴보시길 추천합니다 !👍🏻
중복 있는 순열
주어진 배열 arr에서 필요한 개수만큼 뽑아 순서를 고려해서 나열하는 방법입니다. 이때 하나의 원소를 여러 번 중복해서 사용할 수 있습니다.
즉, 하나의 요소만을 필요한 개수만큼 중복 사용해 하나의 중복순열을 만들 수도 있습니다 ㅎㅎ
순열이기 때문에 같은 요소들로 구성되었어도 순서가 달라지면 다른 배열이 됩니다 !
function getProducts(arr, selectNum) {
const product = [];
const permute = (tmp) => {
if (tmp.length === selectNum) {
product.push(tmp);
return;
}
for (let i = 0; i < arr.length; i++) {
permute([...tmp, arr[i]]);
}
};
permute([]);
return product;
}
const arr = [1, 2, 3, 4];
console.log(getProducts(arr, 2));
getProducts(주어진 배열, 필요한 개수)형태로 함수를 생성합니다.- getProducts 안에서 재귀함수
permute(현재 만들어지는 중인 조합 배열)를 생성합니다.
2-1. 이때 필요한 개수만큼 숫자가 뽑히면if (tmp.length === selectNum)을 통해product에 해당 배열을 저장한 후permute함수를 종료합니다.
2-2. 아니라면 for문을 돌며 재귀함수를 호출하며 순열을 생성합니다. 이때 permute 함수에permute([현재까지 만들어진 배열 + 현재 요소 arr[i]])를 넘깁니다. 같은 요소를 여러 번 넣을 수 있기 때문에 필요한 개수가 될 때까지 계속arr[i]를 추가합니다.
필요한 개수가 될 때까지 재귀함수permute을 호출하고, 만들어진 순열을 product에 넘기고, 실행했던 permute들을 차례로 종료해가며 for문의 idx를 하나씩 증가시킵니다. 이렇게 배열을 전부 돌며 순열을 생성합니다. - for문이 종료되면
return product;을 통해 만들어진 순열들을 반환합니다.
혹시 이해가 잘 안되면 중간중간 console.log()를 찍어보며 흐름을 살펴보시길 추천합니다 !👍🏻
중복 있는 조합
주어진 배열 arr에서 필요한 개수만큼 뽑아 순서를 고려하지 않고 나열하는 방법입니다. 이때 하나의 원소를 여러 번 중복해서 사용할 수 있습니다.
즉, 하나의 요소만을 필요한 개수만큼 중복 사용해 하나의 중복조합을 만들 수도 있습니다 ㅎㅎ
조합이기 때문에 같은 요소들로 구성되었다면 순서가 달라도 같은 배열로 판단합니다.
function getCombinationsWithReplacement(arr, selectNum) {
const combinationsWithReplacement = [];
const combine = (tmp, startIdx) => {
if (tmp.length === selectNum) {
combinationsWithReplacement.push([...tmp]);
return;
}
for (let i = startIdx; i < arr.length; i++) {
combine([...tmp, arr[i]], i);
}
};
combine([], 0);
return combinationsWithReplacement;
}
const arr = [1, 2, 3, 4];
console.log(getCombinationsWithReplacement(arr, 2));
getCombinationsWithReplacement(주어진 배열, 필요한 개수)형태로 함수를 생성합니다.- getCombinationsWithReplacement 안에서 재귀함수
combine(현재 만들어지는 중인 조합 배열, 추가를 시작할 idx)를 생성합니다.
2-1. 이때 필요한 개수만큼 숫자가 뽑히면if (tmp.length === selectNum)을 통해combinationsWithReplacement에 해당 배열을 저장한 후combine함수를 종료합니다.
2-2. 아니라면 for문을 돌며 재귀함수를 호출하며 조합을 생성합니다. 이때 combine함수에combine([현재까지 만들어진 배열 + 추가할 요소], 다음 startIdx)를 넘깁니다. 같은 요소를 여러 번 넣을 수 있기 때문에 필요한 개수가 될 때까지 계속 다음 인덱스로i를 넘깁니다.
필요한 개수가 될 때까지 재귀함수combine을 호출하고, 만들어진 조합을 combinationsWithReplacement에 넘기고, 실행했던 combine들을 차례로 종료해가며 for문의 idx를 하나씩 증가시킵니다. 이렇게startIdx부터 배열의 끝까지 조합을 생성합니다. - for문이 종료되면
return combinationsWithReplacement;을 통해 만들어진 조합들을 반환합니다.
혹시 이해가 잘 안되면 중간중간 console.log()를 찍어보며 흐름을 살펴보시길 추천합니다 !👍🏻
순열 응용문제: 백준 15649번 - N과 M (1)
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [n, m] = fs.readFileSync(filePath).toString().trim().split(" ").map(Number);
const nums = Array.from({ length: n }, (v, i) => i + 1);
const getPermutations = (arr, num) => {
const permutations = [];
const visited = Array(arr.length).fill(false);
const tmp = [];
const permute = (count) => {
if (count == num) {
permutations.push(tmp.join(" "));
return;
}
for (let i = 0; i < arr.length; i++) {
if (!visited[i]) {
visited[i] = true;
tmp.push(arr[i]);
permute(count + 1);
tmp.pop();
visited[i] = false;
}
}
};
permute(0);
return permutations;
};
const result = getPermutations(nums, m);
console.log(result.join("\n"));
매번 slice를 사용해서 배열을 조작하면 효율성이 떨어지기 때문에, visited 배열을 만들어 사용여부를 판단했습니다.
조합 응용문제: 백준 15655번 - N과 M (6)
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [nm, nums] = fs.readFileSync(filePath).toString().trim().split("\n");
const [n, m] = nm.split(" ").map(Number);
const sortedNums = nums
.split(" ")
.map(Number)
.sort((a, b) => a - b);
const getCombinations = (arr, num) => {
const combinations = [];
const tmp = [];
const combine = (count, start) => {
if (count == num) {
combinations.push(tmp.join(" "));
return;
}
for (let i = start; i < arr.length; i++) {
tmp.push(arr[i]);
combine(count + 1, i + 1);
tmp.pop();
}
};
combine(0, 0);
return combinations;
};
const result = getCombinations(sortedNums, m);
console.log(result.join("\n"));
조합 문제에서는 현재 idx보다 앞에 있는 idx는 선택하지 않아야 합니다. 그래서 combine함수에 시작 idx인 start를 같이 넘겨주며 풀었습니다.
중복순열 응용문제: 백준 15665번 - N과 M (11)
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [nm, nums] = fs.readFileSync(filePath).toString().trim().split("\n");
const [n, m] = nm.split(" ").map(Number);
const sortedNums = [
...new Set(
nums
.split(" ")
.map(Number)
.sort((a, b) => a - b)
),
];
const getProduct = (arr, num) => {
const product = [];
const permute = (tmp) => {
if (tmp.length == num) {
product.push(tmp.join(" "));
return;
}
for (let i = 0; i < arr.length; i++) {
permute([...tmp, arr[i]]);
}
};
permute([]);
return product;
};
const result = getProduct(sortedNums, m);
console.log(result.join("\n"));
입력에서 주어진 중복된 숫자는 어차피 숫자 중복으로 뽑을 때 사용되니까 new Set을 사용해서 중복 제거 해주었습니다 ㅎㅎ
중복조합 응용문제: 백준 15657번 - N과 M (8)
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [nm, nums] = fs.readFileSync(filePath).toString().trim().split("\n");
const [n, m] = nm.split(" ").map(Number);
const sortedNums = [
...new Set(
nums
.split(" ")
.map(Number)
.sort((a, b) => a - b)
),
];
const getCombinationsWithReplacement = (arr, num) => {
const combinationsWithReplacement = [];
const combine = (tmp, startIdx) => {
if (tmp.length == num) {
combinationsWithReplacement.push(tmp.join(" "));
return;
}
for (let i = startIdx; i < arr.length; i++) {
combine([...tmp, arr[i]], i);
}
};
combine([], 0);
return combinationsWithReplacement;
};
const result = getCombinationsWithReplacement(sortedNums, m);
console.log(result.join("\n"));
마찬가지로 입력에서 주어진 중복된 숫자는 어차피 숫자 중복으로 뽑을 때 사용되니까 new Set을 사용해서 중복 제거 해주었습니다 ㅎㅎ
데브코스 프론트엔드 5기