你如何从 3 个字符生成所有 5 个字母的字符串?

How do you generate all 5 letter strings from 3 characters?

给定 3 个字符 (abc),我想用它们生成所有可能的 5 个字母的字符串 (aaaaa, aaaab, ... ccccb, ccccc)

const s = 'byg';
const p = [];

for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
        for (let k = 0; k < 3; k++) {
            for (let l = 0; l < 3; l++) {
                for (let m = 0; m < 3; m++) {
                    p.push(s[i] + s[j] + s[k] + s[l] + s[m]);
                }
            }
        }
    }
}

console.log(p, p.length === 3 ** 5)

这感觉是一种低效的方法,那么有没有更多的elegant/efficient方法来做到这一点?

实际上是高效的。您正在尝试生成 3^5 个单词的列表,或者更一般地说,n^k 个单词,其中 n 是字母数,k 是每个单词的长度,因此 O(n^k) 是时间复杂度,因为仅将输出写入内存至少需要 O(n^k) 时间。 k 个嵌套循环,每个循环都有 n 次迭代,为您提供了这个下限。没有比这更好的了。

问题是依赖硬编码嵌套循环的可扩展性不是很好。如果你想要长度为 10 或 20 甚至更长的单词怎么办?递归方法可能更好。


编辑:

想想看,下界实际上是 O(k*n^k),因为您有 n^k 个单词,每个单词的长度为 k。但除此之外,我认为我的分析仍然是正确的。这些循环仍然达到下限。

你写了一个组合算法,但是如果你有一个字段是好的,你只能做长度为3的概率,因为你需要重新做

function permutationAndCombination(source = [], selectedLimit, isPermutation = true) {
  if (!Array.isArray(source)) return source

  source = [...new Set(source)]
  selectedLimit = selectedLimit || source.length

  const result = []
  const sourceLen = source.length

  selectedLimit = selectedLimit > sourceLen ? sourceLen : selectedLimit

  const innerLoop = (prefix = [], done = [], index = 0) => {
    const prefixLen = prefix.length

    for (let i = isPermutation ? 0 : index; i < sourceLen; i++) {

      if (prefixLen > selectedLimit - 1) break

      // Optimization: Continue to next cycle if current item has be already used for 'prefix'.
      if (done.includes(i)) continue

      const item = source[i]
      const newItem = [...prefix, item]

      if (prefixLen === selectedLimit - 1) {
        result.push(newItem)
      }

      if (prefixLen < selectedLimit - 1) {
        innerLoop(newItem, [...done, i], index++)
      }

    }
  }

  if (source.length) {

    // there is only one case if we want to select all items from source by combination.
    if (!isPermutation && selectedLimit === sourceLen) {
      return source
    }

    innerLoop()
  }

  return result
}

console.log(permutationAndCombination(['a','b','c'], 3));

希望能帮到你

您的嵌套 for 循环确实暗示代码可以重构 使用递归或在我下面的示例中通过创建 更高级别的循环。

这种方法允许我们生成任意长度的字符串。

let characters = "abc";
let desiredLength = 5;

let theSet = [""];
for ( let length = 0; length < desiredLength; length++){
    let extendedSet = [];
    theSet.forEach( (item) => 
        extendedSet.push( ...extendWith( item, characters) )
    )
    theSet = extendedSet; 
}

console.log('result ', theSet);
   
// given a strings and a set of characters
// generate an array of string extended with each
// of the characters. 
// "a" with "xy" generates
// [ "ax", "ay" ]
function extendWith( extendThis, characters){
    let result = [];
    [...characters].forEach( (c) => result.push(extendThis+c) );
    return result;
}

我们可以像这样使 extendWith 函数更简洁

function extendWith( extendThis, characters){   
   return [...characters].map( c => extendThis + c );  
}

因为它现在只是一行表达式,所以我们可以省去效用函数并进一步简化

for ( let length = 0; length < desiredLength; length++){

    theSet = theSet.flatMap( (item) => 
        [...characters].map( c => item + c )
    );

}