代码之家 › 专栏 › 技术社区 › OfirD

生成字符串的所有谐音

algorithm javascript

OfirD · 技术社区 · 7 年前

我想生成给定弦的所有协和音。

谐音是通过重复来识别的一种文体手段。指相邻单词中相同或相似的辅音,其元音声音是不同的。( Wikipedia )

一 consonant 是表示辅音的字母表中的一个字母。下表同化了英语辅音组,为保持简单(isic)提供了以下便利:

它忽略了图表(“sh”、“ch”、“th”等)。
它忽略了元音。
它忽略了“h”、“y”、“w”、“x”。
它假定一个给定的字母只能是一个辅音群的成员。因此,“c”与“s”和“z”一起(随机地),而“g”与“j”一起。

我们还假设允许并且应该忽略符合案例2和3的输入。但是,如果输入符合案例1,或者它破坏了案例4(参见下面的示例),则输入无效。

所以:

var consonants = [
    ['b', 'p'],
    ['c', 's', 'z'],
    ['d', 't'],
    ['f', 'v'],
    ['g', 'j'],
    ['k', 'q']
];

例如,给定字符串 "jedi" ,输出应为:

var consonances = ["gedi", "jeti", "geti"]

注意,“e”和“i”——誓言(案例2)——可以作为输入。

其他一些例子:

"btb"       --> ["ptb", "pdb", "pdp", "bdb", "bdp", "btp", "ptp"]
"star"      --> ["ctar", "ztar", "sdar", "cdar", "zdar"]

无效输入:

Diagraphs: "show", "chair", "high", "the"
破案4: "sure", "cat", "good"

我在想办法接近它时撞到了墙上。我讨论了排列问题,因为我想它们可能在这里是相关的,但是我不知道如何在这里应用这样的解决方案。

我需要一个算法,但是一个完整的代码解决方案是很好的,当然。我将在此处添加我当前剩余的内容(JS代码):

const irrelvant = ['a', 'e', 'i', 'o', 'u', 'h', 'y', 'w', 'x'];
function isConsonant(c) {
   return !irrelvant.includes(c);
}
function getConsonants(c) {
   let curConsonants = [];
   consonants.every((group) => {
      if (group.includes(c)) {
         curConsonants = group;
      };
      return !curConsonants.length;
   });
   return curConsonants;
}

3 回复 | 直到 7 年前

Stefan Haustein 7 年前

我建议把相关辅音组织在地图上:

var consonants = {
  "b": "p",
  "p": "b",
  "c": "sz",
  "s": "cz",
  "z": "cs",
  "d": "t",
  "t": "d",
  "f": "v",
  "v": "f",
  "g": "j",
  "j": "g",
  "k": "q",
  "q": "k", 
];

现在可以逐字符迭代字符串。如果您在映射中碰到一个字符,那么考虑将映射字符串中的每个字符插入pos(除了不变的递归之外,您还可以这样做)。Pseudocode:

function generate(word, pos) {
   if (pos == word.length) {
     console.log(word);
     return;
   }
   generate(word, pos + 1);
   mapped = consonants[word.charAt(pos)];
   if (mapped != null) {
     var prefix = word.substring(0, pos);
     var suffix = word.substring(pos + 2);
     for (var i = 0; i < mapped.length; i++) {
       var changed =  prefix + mapped.charAt(i) + suffix; 
       geneate(changed, pos + 1);
     }
   }
 }

Some Guy 7 年前

我可以给你一个简单的算法,如何使用递归算法在Python中完成它。

import itertools

consonants = [['b', 'p'],
    ['c', 's', 'z'],
    ['d', 't'],
    ['f', 'v'],
    ['g', 'j'],
    ['k', 'q']]

# Create a map to indicate which group can the letter be found in
sound = {} # These are actually index of groups for letters
for i,a_group in enumerate(consonants):
    for letter in a_group:
        sound[letter] = i # b, p have the sound 0, c,s,z have sound 1 etc

def getConsonantsRec(c, options):
    if len(c) > 0:
        if c[0] in sound:
            options.append(consonants[sound[c[0]]]) # Add all letters as the option at this place
        else:
            options.append([c[0]]) #Only this letter at this place
        getConsonantsRec(c[1:],options) #Make string shorter each call
    return

def getConsonants(c):
    options = []
    getConsonantsRec(c,options)
    return [x for x in itertools.product(*options)] #Generate the combinations from the options at each place

allConsonants = getConsonants('star')
print(allConsonants)

输出:

[('c', 'd', 'a', 'r'), ('c', 't', 'a', 'r'), ('s', 'd', 'a', 'r'), ('s', 't', 'a', 'r'), ('z', 'd', 'a', 'r'), ('z', 't', 'a', 'r')]

现在您可以通过添加对图表、元音等的检查来进一步增强这一点。

OfirD 7 年前

其他的解决方案帮助我节省了一分钱:这是一个简单的笛卡尔积问题。拿 implementation 这符合你的需要,你就完成了。例如:

console.log(...getConsonances('stars').map(con => con.join('')));

function getConsonances(s) {
    let combConsonants = [];
    let idx = 0;
    s.split('').forEach((c) => {
       const curConsonants = getConsonants(c);
       if (curConsonants.length) {
           combConsonants.push(curConsonants);
           idx++;
       } else {
           let notConsonant = [combConsonants[idx] ? combConsonants[idx] : [], c].join('');
           combConsonants.splice(idx, 1, [notConsonant]); 
       }
    }); 
    return cartesianProduct(combConsonants);
}
function getConsonants(c) {
   const consonants = [
    ['b', 'p'],
    ['c', 's', 'z'],
    ['d', 't'],
    ['f', 'v'],
    ['g', 'j'],
    ['k', 'q']
]; 
   let curConsonants = [];
   consonants.every((group) => {
      if (group.includes(c)) {
         curConsonants = group;
      };
      return !curConsonants.length;
   });
   return curConsonants;
}
function cartesianProduct(arr) {
  return arr.reduce((a, b) =>
    a.map(x => b.map(y => x.concat(y)))
    .reduce((a, b) => a.concat(b), []), [[]]);
}