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

Question

给定 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方法来做到这一点？

Answer 1

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

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

编辑：

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

Answer 2

你写了一个组合算法，但是如果你有一个字段是好的，你只能做长度为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));

希望能帮到你

Answer 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 )
    );

}

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

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

javascript

combinations