你如何从 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 )
);
}
给定 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 )
);
}