为字符串的所有排列复制每个字符

Question

这是一个略odd/unique的请求。我正在尝试实现一个结果，例如“yes”变成“yyes”、“yees”、“yess”、“yyees”、“yyess”、“yyeess”。

我看过这个：完成了它的大写，但是我的理解是禁止我将其操纵成字符重复（如果这种方法甚至可以这样使用的话）。

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;

        

    }

如果我没有特别清楚地解释这一点，请告诉我，我会澄清的。我觉得这很有挑战性！

Answer 1

总体思路
要获得我们可以从有序字母数组中获得的所有单词的列表，我们需要获得字母的所有组合，将 1 或 2 次传递给单词，例如：

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

所有可能单词的数量等于 2 ^ word.length（8 对应 "yes"），因此我们可以构建二进制 table，其中 8 行表示所有可能的组合通过将数字从 0 转换为 7（从十进制到二进制）：

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

我们可以将每个小数用作新单词的模式，其中 0 表示字母必须使用一次，而 1 - 字母必须使用两次：

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

代码
因此，您的代码表示可能如下所示：

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

Answer 2

也许这个例子可以帮到你。它有点不整洁也不是最佳的，但它似乎有效：

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

javascript

permutation

duplicates

typescript