Having fun with permutations

unique-letter-combination-permutation.ts

// example usage
const chars = "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z".split(' ');
const limit = 2;
console.log(generator(limit, chars));



/**
*  Unique letter combination permutations generator that only generates unique strings like   
*   'AB', 'AC', 'AD', 'AE', 'AF', 'AG', 'AH', 'AI', 'AJ', 'AK',
*   'AL', 'AM', 'AN', 'AO', 'AP', 'AQ', 'AR', 'AS', 'AT', 'AU',
*   'AV', 'AW', 'AX', 'AY', 'AZ', 'BC', 'BD', 'BE',...
*
*  A string sequence is considered VALID if ALL of following are true:
*   1) Has unique letter combinations
*   2) Each letter can be only be used once
*   3) If the sequence is sorted should still be unique: for example if we have 'AB' we don't allow 'BA', if 'ABC' we can't have 'BCA' etc... !

 * @param limit The number of chars that each sequence should have
 * @param chars The chars that will be used for the generation
 * @returns Array<string>
 */
export function uniqueLetterCombinations(limit: number, chars: Array<string>): Array<string> {
  let res = new Map<string, boolean>();
  let path: Array<string> = [];
  let seen = new Set<string>();

  backtracking(limit, path, seen, res);

  return Array.from(res.keys());

  function backtracking(limit: number, path: string[], seen: Set<string>, res: Map<string, boolean>) {
    const sortedPath = [...path].sort().join("")
    if (res.has(sortedPath)) {
      return;
    }
    if (limit === path.length) {
      res.set(sortedPath, true);
      return;
    }
  
    for (let l in chars) {
      if (seen.has(chars[l])) continue;
  
      seen.add(chars[l]);
      path.push(chars[l]);
  
      backtracking(limit, path, seen, res);
  
      seen.delete(chars[l]);
      path.pop();
    }
  }
}