1

I am looking for this stackoverflow question to be answered in Javascript.

So if my input is "word", the function should return:

word, Word, wOrd, WOrd, woRd, WoRd, etc..

here's what i have so far but it only produces the permutations (doesn't capitalize anything)

var perm = function(str){
var results = [];

var combos = function(reference, appendTo){
 appendTo = appendTo || "";
 if(reference.length === 0) {
  results.push(appendTo);
 }
 for(var i = 0; i < reference.length; i++){
  var current = reference.splice(i, 1);
  combos(reference, appendTo+current);
   reference.splice(i, 0, current)
 }
} 
combos(str.split(""));
return results;
}
perm("word");
Community
  • 1
  • 1
user3068590
  • 59
  • 1
  • 5

3 Answers3

7

One option would be generating capitalization permutations via binary logic.

As a simple example of the snippet below, consider the following table where the left column is the binary representation of the current permutation and the right column is the resulting capitalization:

0000 | word
1000 | Word
0100 | wOrd
1100 | WOrd
...
1111 | WORD


// Used to display the results
const write = (msg) => {
  document.body.appendChild(document.createElement('div')).innerHTML = msg;
};

const input = "word";
const letters = input.split("");
const permCount = 1 << input.length;

for (let perm = 0; perm < permCount; perm++) {
  // Update the capitalization depending on the current permutation
  letters.reduce((perm, letter, i) => {
    letters[i] = (perm & 1) ? letter.toUpperCase() : letter.toLowerCase();
    return perm >> 1;
  }, perm);

  const result = letters.join("");
  write(result);
}

Note that theoretically this approach would work all the way up to Number.MAX_SAFE_INTEGER, up to inputs of length 52, but realistically you'll run into performance issues.

Etheryte
  • 24,589
  • 11
  • 71
  • 116
  • thanks this works well. Can you explain how the second for loop works? Specifically I am wondering how it breaks out of the loop, I am not use to seeing for loops written this way. – user3068590 Jan 19 '15 at 19:55
  • Using `for(...; j; ...)` is equivalent to `for(...; j !== 0; ...)`. Note the positioning of semicolons in the above code. We initialize two variables in the inner loop, then check the condition and then perform two operations on each iteration. While it isn't clean style-wise, it's rather straight forward if you're familiar with the concept of binary permutations. – Etheryte Jan 19 '15 at 20:41
  • Nit what if permutation of "word" but only 2 of characters are uppercased? – Roi May 25 '15 at 09:34
  • @Roi You can either add some additional checks to the above code to only keep the ones you want or write a slightly different method which only generates combinations with 2 uppercase chars. – Etheryte May 25 '15 at 11:57
1

var s = "word";
var sp = s.split("");
for (var i = 0, l = 1 << s.length; i < l; i++) {
  for (var j = i, k = 0; j; j >>= 1, k++) {
    sp[k] = (j & 1) ? sp[k].toUpperCase() : sp[k].toLowerCase();
  }
  var st = sp.join("");
  var d = document.createElement("p");
  d.appendChild(document.createTextNode(st));
  document.body.appendChild(d);
}
Hea Ter Makav
  • 19
  • 1
  • Consider replacing line 2 with `var sp = s.toLowerCase().split("");`, otherwise you will have twice the uppercase letters and no lowercase in the result for all uppercase inputs. E.g., `var s = "WORD"`. – saulotoledo Sep 11 '22 at 08:56
0

With Nit's solution in mind, I wanted to offer a slightly refactored solution that may be easier to follow

  var perm = function(str){
    var results = [];
    var arr = str.split("");
    var len = Math.pow(arr.length, 2);

    for( var i = 0; i < len; i++ ){
      for( var k= 0, j = i; k < arr.length; k++, j >>=1){
        arr[k] = ( j & 1 ) ? arr[k].toUpperCase() : arr[k].toLowerCase();
      }
      var combo = arr.join("");
      results.push(combo);
    }
    return results;
  }

  perm("word");
user3068590
  • 59
  • 1
  • 5