Skip to content
Advertisement

Duplicating each character for all permutations of a string

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!

Advertisement

Answer

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;
}
User contributions licensed under: CC BY-SA
5 People found this is helpful
Advertisement