CODEWITHSUNDEEP
javascriptcombinations
Siddharth Shyniben
Siddharth Shyniben

Reputation: 772

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

Given 3 characters (abc), I want to generate all possible 5-letter strings with them (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)

This feels like an inefficient way to do this, so is there a more elegant/efficient way to do this?

Upvotes: 1

Views: 348

Answers (3)

djna
djna

Reputation: 55907

Your nested for loops does imply that code can be refactored either using recursion or as in my example below by creating a higher level loop.

This approach allows us to generate strings of any desired length.

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;
}

We can make that extendWith function more succinct like this

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

and as it's now just a one line expression we can dispense with the utility function and simplify a bit more

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

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

}

Upvotes: 1

vueAng
vueAng

Reputation: 453

You write a combination algorithm, but if you have a field that is a good one, you can only do the probability of length 3, because you need to do it again

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

Hope to help you

Upvotes: 1

Orius
Orius

Reputation: 1093

It is in fact efficient. You are trying to produce a list of 3^5 words, or more generally, n^k words, where n is the number of letters and k is the length of each word, so O(n^k) is a lower bound on the time complexity, as just writing the output to the memory takes at least O(n^k) time. k nested loops each with n iterations gives you this lower bound. You cannot do better than that.

The problem is that relying on hardcoded nested loops is not very scalable. What if you wanted words of length 10 or 20 or even more? Recursive approach might be better.

Edit:

Come to think of it, the lower bound is actually O(k*n^k), as you have n^k words each of length k. But other than that I think my analysis is still correct. Those loops still achieve the lower bound.

Upvotes: 0

Related Questions