Как упростить перебор всех комбинаций

Question

Есть объект:

const letters = {
    1: ['a', 'b', 'c'],
    2: ['d', 'e', 'f'],
    3: ['g', 'h', 'i'],
    4: ['j', 'k', 'l'],
    5: ['m', 'n', 'o'],
    6: ['p', 'q', 'r'],
    7: ['s', 't', 'u'],
    8: ['v', 'w', 'x'],
    9: ['y', 'z']
}

Необходимо написать функцию, которая вернет все возможные комбинации из переданных строкой чисел. Я сделал таким образом:

const func = (str) => {
  if (str.length === 0) return []

  const strArr = str.split('')
  const result = []
  
  const arrays = strArr.map(item => letters[item])

  if (strArr.length === 1) return arrays[0]
  
  for (let letterIndex = 0; letterIndex < arrays[0].length; letterIndex++) {
    const word = arrays[0][letterIndex]

    for (let arrayIndex = 1; arrayIndex < arrays.length; arrayIndex++) {
      
      for (let letterArrayIndex = 0; letterArrayIndex < arrays[arrayIndex].length; letterArrayIndex++) {
        const secondWord = word + arrays[arrayIndex][letterArrayIndex]
        
        if (arrays.length > 2) {
          for (let restArrays = arrayIndex + 1; restArrays < arrays.length; restArrays++) {
            for (let i = 0; i < arrays[restArrays].length; i++) {
              result.push(secondWord + arrays[restArrays][i])
            }
          }
        } else {
          result.push(secondWord)
        }
      }
    }
  }
  
  return result
}

Ожидаемые выводы:

func('') => []
func('2') => ['d', 'e', 'f']
func('23') => ["dg","dh","di","eg","eh","ei","fg","fh","fi"]

Но очевидно, что это выглядит стремно. Я чувствую, что это можно решить как то красиво рекурсией, но в голову не лезет, как это сделать.

Answer 1

Требование func('') => [] я заменил на func('') => ['']. Так более логично.

     const letters = {
        1: ['a', 'b', 'c'],
        2: ['d', 'e', 'f'],
        3: ['g', 'h', 'i'],
        4: ['j', 'k', 'l'],
        5: ['m', 'n', 'o'],
        6: ['p', 'q', 'r'],
        7: ['s', 't', 'u'],
        8: ['v', 'w', 'x'],
        9: ['y', 'z']
    }
    
    const func = digits => {
        if (digits.length === 0) {
            return [''];
        }
        const result = [];
        const strs = func(digits.substring(1));
        for (const c of letters[+digits[0]]) {
            for (const s of strs) {
                result.push(c + s);
            }
        }
        return result;
    };
    
    console.log(func('23'));

Answer 2

Вариант без рекурсии:

const letters = {
    1: ['a', 'b', 'c'],
    2: ['d', 'e', 'f'],
    3: ['g', 'h', 'i'],
    4: ['j', 'k', 'l'],
    5: ['m', 'n', 'o'],
    6: ['p', 'q', 'r'],
    7: ['s', 't', 'u'],
    8: ['v', 'w', 'x'],
    9: ['y', 'z']
};

const getAllCombinationsOfTwoArr = (arr1, arr2) => {
  const result = [];
  
  for (const str1 of arr1) {
    for (const str2 of arr2) {
      result.push(str1 + str2);
    }
  }
  
  return result;
}

const getAllCombinations = (str, alphabet) => {
  if (str.length === 0) return [];
  
  const rowsNum = str.split('');
  let result = [''];
  
  for (const rowNum of rowsNum) {
    result = getAllCombinationsOfTwoArr(result, alphabet[rowNum]);
  }
  
  return result;
}

console.log(getAllCombinations('', letters));
console.log(getAllCombinations('1', letters));
console.log(getAllCombinations('12', letters));
console.log(getAllCombinations('123', letters));

БЛОГ НА HUSL

Как упростить перебор всех комбинаций

Ответы (2 шт):