[Algo] Javascript helper functions 총 정리

자료구조를 위한 특별한 내장 컬렉션이 미비한 Javascript 알고리즘 문제 풀이를 위해 다양한 Helper function들을 구현해보았다.

1.Permutation(순열)

/// DFS, easiest
/// O(n^k) => (arr.length^num)
function getPermutation (arr, num) {
  let result = [];

  const dfs = (temp) => {
    if(temp.length === num) return result.push(temp)
    for(let i=0; i<arr.length; i++){
      dfs([...temp, arr[i]])
    }
  }
  dfs([], num)
  return result;
}

/// Recursive, fastest 1
// O(n!)
function getPermutations(arr, num) {
  const result = [];
  if(num === 1) return arr.map(v => [v]);
  
  arr.forEach((item, i, origin) => {
    const rest = origin.slice(i+1);

    const permutations = getPermutations(rest ,num - 1);
    const temp = permutations.map((perm) => [item, ...perm]);
    result.push(...temp);
  })

  return result;
}

/// Heap, fastest 2
/// O(n!)
function generatePermutations(arr, result, n = arr.length) {
  if (n === 1) {
    result.push([...arr]);
    return;
  }

  for (let i = 0; i < n; i++) {
    generatePermutations(arr, result, n - 1);
    const j = n % 2 === 0 ? i : 0;
    [arr[n - 1], arr[j]] = [arr[j], arr[n - 1]];
  }
}

function getPermutations(arr) {
  const result = [];
  generatePermutations(arr, result);
  return result;
}

2. Combinations

// easy, recuresive
var combine = function(n, k) {
    const arr = Array.from({length:n}).map((item, index) => item = index +1 );
   
    const getCombinations = (arr, m) => {
        if(m === 1) return arr.map(v => [v])
        const result = [];
       
        arr.forEach((item, index, origin) => {
            const rest = origin.slice(index+1);
            const combinations = getCombinations(rest, m-1);
    
            combinations.map(comb => result.push([item, ...comb]))
       
        })
    
        return result; 
    }
    return getCombinations(arr,k)
};

// iterative, most efficient
function combine(n, k) {
    let results = [];
    let stack = [];

    stack.push({index: 1, combination: []});

    while (stack.length > 0) {
        let {index, combination} = stack.pop();

        // When the combination is of length k, add it to the results
        if (combination.length === k) {
            results.push(combination);
            continue;
        }

        // Iterate through the numbers
        for (let i = index; i <= n; ++i) {
            // Create a new combination from the current one and push it onto the stack
            stack.push({index: i + 1, combination: [...combination, i]});
        }
    }

    return results;
}

3.PowerSet(멱집합: 모든 부분집합)

/// DFS
const getPowerSet = (arr) => {
  const res = [];

  const dfs = (temp ,start) => {
    res.push(temp);
    if (temp.length === arr.length) return;

    for (let i = start; i < arr.length; i++) {
      dfs([...temp, arr[i]], i + 1);
    }
  };
   dfs([], 0);

  return res;
};

4.Subsequences(부분수열)

  const arr = [];
  const dfs = (currChArr, currIndex) => {
    if (currIndex >= s.length) return;
  
	...
    const newChArr = [...currChArr, s[currIndex]];

    dfs(currChArr, currBits, currIndex + 1);
    dfs(newChArr, currIndex + 1);
  };
  dfs([], 0, 0);

Unique characters combined string

stringA.length !== new Set(stringA.split('')).size