[Algorithm] 백트래킹: 순열과 조합

순열

• 정의: 순서에 의미가 있으며, 중복 없이 n개의 요소 중 m개를 선택하는 경우의 수.
• 예시: n = 3, m = 2일 때, [1, 2, 3]에서 2개의 요소를 선택하는 순열은 [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, m] = input.shift().split(" ").map(Number);
let arr = [];

for (let i = 1; i <= n; i++) arr.push(i);

let visited = new Array(n).fill(false);
let selected = [];

let answer = "";

function dfs(arr, depth) {
  if (depth == m) {
    let result = [];
    for (let i of selected) result.push(arr[i]);
    answer += result.join(" ") + "\n";
    return;
  }

  for (let i = 0; i < arr.length; i++) {
    if (visited[i]) continue;
    selected.push(i);
    visited[i] = true;
    dfs(arr, depth + 1);
    selected.pop();
    visited[i] = false;
  }
}

dfs(arr, 0);
console.log(answer.trim());
// Output: [ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]

조합

• 정의: 순서에 의미가 없으며, 중복 없이 n개의 요소 중 m개를 선택하는 경우의 수.
• 예시: n = 3, m = 2일 때, [1, 2, 3]에서 2개의 요소를 선택하는 조합은 [1, 2], [1, 3], [2, 3]

let visited = new Array(n).fill(false);
let selected = [];

let answer = "";

function dfs(arr, depth, start) {
  if (depth == m) {
    let result = [];
    for (let i of selected) result.push(arr[i]);
    for (let x of result) answer += x + " ";
    answer += "\n";
    return;
  }

  for (let i = start; i < arr.length; i++) {
    if (visited[i]) continue;
    selected.push(i);
    visited[i] = true;
    dfs(arr, depth + 1, i + 1);
    selected.pop();
    visited[i] = false;
  }
}

dfs(arr, 0, 0);
console.log(answer);

// Output: [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]

중복순열

• 정의: 순서에 의미가 있으며, 중복을 허용하여 n개의 요소 중 m개를 선택하는 경우의 수.
• 예시: n = 3, m = 2일 때, [1, 2, 3]에서 2개의 요소를 중복을 허용해 선택하는 경우는 [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]

// 중복순열 함수
function repeatedPermutation(arr, m) {
  let selected = [];
  let answer = "";

  function dfs(depth) {
    if (depth === m) {
      answer += selected.map(i => arr[i]).join(' ') + '\n';
      return;
    }

    for (let i = 0; i < arr.length; i++) {
      selected.push(i);
      dfs(depth + 1);
      selected.pop();
    }
  }

  dfs(0);
  return answer;
}
// Output: [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ] ]

중복조합

• 정의: 순서에 의미가 없으며, 중복을 허용하여 n개의 요소 중 m개를 선택하는 경우의 수.
• 예시: n = 3, m = 2일 때, [1, 2, 3]에서 2개의 요소를 중복을 허용해 선택하는 경우는 [1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]

// 중복조합 함수
function repeatedCombination(arr, m) {
  let selected = [];
  let answer = "";

  function dfs(depth, start) {
    if (depth === m) {
      answer += selected.map(i => arr[i]).join(' ') + '\n';
      return;
    }

    for (let i = start; i < arr.length; i++) {
      selected.push(i);
      dfs(depth + 1, i);
      selected.pop();
    }
  }

  dfs(0, 0);
}
// Output: [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 2 ], [ 2, 3 ], [ 3, 3 ] ]