Duplicating each character for all permutations of a string

Question

This is a slightly odd/unique request. I am trying to achieve a result where e.g "yes" becomes, "yyes", "yees", "yess", "yyees", "yyess", "yyeess".

I have looked at this: Find all lowercase and uppercase combinations of a string in Javascript which completes it for capitalisation, however my understanding is prohibiting me from manipulating this into character duplication (if this method is even possible to use in this way).

export function letterDuplication(level: number, input: string){

const houseLength = input.length;
if (level == 1){

    var resultsArray: string[] = [];
    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) => {
          
        if (perm & 1) {
        letters[i] = (letter.slice(0, perm) + letter.slice(perm-1, perm) + letter.slice(perm));
        } else {
        letters[i] = (letter.slice(0, perm - 1) + letter.slice(perm, perm) + letter.slice(perm))
        
      }
          return perm >> 1;
        }, perm);
        
        var result = letters.join("");
        console.log(result);
        resultsArray[perm] = result;

        

    }

If I haven't explained this particularly well please let me know and I'll clarify. I'm finding it quite the challenge!

You need to show more code of how you are thinking. But you could use a regex, and then a for loop to go through the results. — Krullmizter, Dec 28 '21 at 15:14
@Krullmizter I did link the other page containing the code I was basing it off of, but I've edited it now. — Seb Lawrence, Dec 28 '21 at 15:26

score 0 · Accepted Answer · answered Dec 28 '21 at 15:50

General idea
To get the list of all words we can get from ordered array of letters, we need to get all combinations of letters, passed 1 or 2 times into word, like:

word = 'sample'
array = 's'{1,2} + 'a'{1,2} + 'm'{1,2} + 'p'{1,2} + 'l'{1,2} + 'e'{1,2}

Amount of all possible words equal to 2 ^ word.length (8 for "yes"), so we can build binary table with 8 rows that represent all posible combinations just via convering numbers from 0 to 7 (from decimal to binary):

0 -> 000
1 -> 001
2 -> 010
3 -> 011
4 -> 100
5 -> 101
6 -> 110
7 -> 111

Each decimal we can use as pattern for new word, where 0 means letter must be used once, and 1 - letter must be used twice:

0 -> 000 -> yes
1 -> 001 -> yess
2 -> 010 -> yees
3 -> 011 -> yeess
4 -> 100 -> yyes
5 -> 101 -> yyess
6 -> 110 -> yyees
7 -> 111 -> yyeess

Code
So, your code representation may looks like this:

// Initial word
const word = 'yes';
// List of all possible words
const result = [];

// Iterating (2 ^ word.length) times
for (let i = 0; i < Math.pow(2, word.length); i++) {
    // Get binary pattern for each word
    const bin = decToBin(i, word.length);
    // Make a new word from pattern ...
    let newWord = '';
    for (let i = 0; i < word.length; i++) {
        // ... by adding letter 1 or 2 times based on bin char value
        newWord += word[i].repeat(+bin[i] ? 2 : 1);
    }
    result.push(newWord);
}

// Print result (all possible words)
console.log(result);


// Method for decimal to binary convertion with leading zeroes
// (always returns string with length = len)
function decToBin(x, len) {
    let rem, bin = 0, i = 1;
    while (x != 0) {
        rem = x % 2;
        x = parseInt(x / 2);
        bin += rem * i;
        i = i * 10;
    }
    bin = bin.toString();
    return '0'.repeat(len - bin.length) + bin;
}

score 0 · Answer 2 · answered Dec 28 '21 at 16:17

Maybe this example can help you. It's a bit not neat and not optimal, but it seems to work:

function getCombinations(word = '') {
  const allCombination = [];
  const generate = (n, arr, i = 0) => {
    if (i === n) {
      return allCombination.push([...arr]);
    } else {
      arr[i] = 0;
      generate(n, arr, i + 1);
      arr[i] = 1;
      generate(n, arr, i + 1);
    }
  }
  generate(word.length, Array(word.length).fill(0));

  return allCombination.map((el) => {
    return el.map((isCopy, i) => isCopy ? word[i].repeat(2) : word[i]).join('')
  });
}

console.log(getCombinations('yes'));
console.log(getCombinations('cat'));

Duplicating each character for all permutations of a string

2 Answers2